Archives

Archives de présentations des années précédentes:

Les 8 et 9 octobre 2015 : journées de lancement de Graphes@Lyon

Vendredi 20 novembre 2015 à 11h au LIRIS : Mourad Baiou (CNRS, LIMOS)

Vendredi 4 décembre 2015 à 14h au LIP (ENS de Lyon), amphi B: Jan Volec (ETH Zürich)

Title: Graph limit approach in extremal combinatorics

Abstract: In the last decade, a theory of combinatorial limits emerged, and attracted a substantial attention. In the first part of the talk, we focus on limits of dense graphs and describe a counterexample to a conjecture of Lovasz and Szegedy on the structure of the topological space of typical vertices of the limit objects.
We will also apply the so-called flag algebra method to a conjecture of Erdos and Sos on number of rainbow triangles in 3-edge-colored graphs. In the second part of the talk, we will show that weakly quasirandom 3-graphs where every 4 vertices span at most two edges have density at most 1/4. This was conjectured by Erdos, and the constant 1/4 is best possible.

Vendredi 11 mars 2016, à 10h au LIRIS, Nautibus, salle C3 (acces) : Eric Tannier (INRIA, LBBE)

Title : On random graphs and the evolution

Abstract: The 1960 paper of Erdös and Renyi was entitled "On the evolution of random graphs". They mention possible applications in many fields, but not in evolution. I will show such an application. Evolution on genomic sequences will be an accumulation of inversions. I will show that this process is, with a reasonable approximation, similar to the accumulation of edges in a graph, where each vertex i is associated with a probability p_i, and an edge is taken with probability p_ip_j. This analogy is helpful to estimate unknown parameters (how many inversions i.e. edges?) from observable ones (how many conserved adjacencies i.e. isolated vertices?).

Vendredi 18 mars 2016, à 10h, au LIP, salle B1 : Pierre Aboulker (Université de Nice Sophia antipollis, équipe COATI)

Title : Configurations in digraphs

Vendredi 13 mai 2016, à 10h au LIRIS, salle C1 : Guillem Perarnau (Université de Birmingham)

Title: Stability of bridge-addable graph classes.

Abstract: A class of graphs is bridge-addable if, given a graph G in the class, any graph obtained by adding an edge between two connected components of G is also in the class. Examples of such graph classes are forests, planar graphs and graphs with bounded treewidth.
McDiarmid, Steger and Welsh showed that graphs in bridge-addable classes are likely to be connected. Moreover, they conjectured that the class of all forests is the bridge-addable class whose elements are less likely to be connected. We prove that even a stronger version of this conjecture is true: not only forests are the worst bridge-addable class with respect to connectivity, but they are the unique worst one. In other words, any bridge-addable class with not too many connected elements looks very similar to the class of all forests (stability). This is joint work with Guillaume Chapuy.

Vendredi 27 mai 2016, à 10h au LIP, salle B1 : Eun Jung Kim.

Titre : The “art of trellis decoding” is fixed-parameter tractable

Résumé : Given n subspaces of a finite-dimensional vector space over a fixed finite field, we wish to find a linear layout V1,V2,…,Vn of the subspaces such that dim((V1+V2+⋯+Vi)∩(Vi+1+⋯+Vn))≤k for all i, such a linear layout is said to have width at most k. When restricted to 1-dimensional subspaces, this problem is equivalent to computing the trellis-width (or minimum trellis state-complexity) of a linear code in coding theory and computing the path-width of an -represented matroid in matroid theory.
We present a fixed-parameter tractable algorithm to construct a linear layout of width at most k, if it exists, for input subspaces of a finite-dimensional vector space over . As corollaries, we obtain a fixed-parameter tractable algorithm to produce a path-decomposition of width at most k for an input -represented matroid of path-width at most k, and a fixed-parameter tractable algorithm to find a linear rank-decomposition of width at most k for an input graph of linear rank-width at most k. In both corollaries, no such algorithms were known previously.
It was previously known that a fixed-parameter tractable algorithm exists for the decision version of the problem for matroid path-width, a theorem by Geelen, Gerards, and Whittle~(2002) implies that for each fixed finite field , there are finitely many forbidden -representable minors for the class of matroids of path-width at most k. An algorithm by Hlineny (2006) can detect a minor in an input -represented matroid of bounded branch-width. However, this indirect approach would not produce an actual path-decomposition. Our algorithm is the first one to construct such a path-decomposition and does not depend on the finiteness of forbidden minors.

Vendredi 10 juin 2016, à 10h au LIRIS, bâtiment Nautibus, salle TD10: Yohann Benchetrit, TBA.

Titre: On the chromatic number of t-perfect graphs

Abstract: The stable set polytope STAB(G) of a graph G is the convex hull of the incidence vectors of its stable sets. It is a well-known result of polyhedral combinatorics that non-negativity and edge inequalities are enough to completely describe STAB(G) if and only if G is bipartite. As defined by Chvátal, a graph G is t-perfect if STAB(G) is completely described by non-negativity, edge inequalities and odd circuit inequalities (equivalently, G is t-perfect if and only if the Chvátal rank of the edge relaxation of STAB(G) is at most 1). T-perfect graphs are K4-free, and results of Lovász, Fulkerson and Chvátal imply that every perfect K4-free graph is t-perfect.

Whereas every perfect K4-free graph is obviously 3-colorable, it is still unknown whether the chromatic number of t-perfect graphs is bounded by a constant.
Laurent and Seymour found a t-perfect graph of chromatic number 4, and no t-perfect graph with a greater chromatic number is known.

In this talk, I will show a new example of a (minimally) 4-chromatic t-perfect graph, and prove that this and the example of Laurent and Seymour are the only 4-chromatic graphs in a relatively wide subclass of t-perfect graphs. The talk will end with open problems and questions.

Vendredi 7 octobre 2016 à 10h au LIRIS: Marc Heinrich (LIRIS)

Titre : Coloriage avec des conflits et algorithmes distribués.

Résumé : Le modèle LOCAL est un modèle de calcul distribué dans lequel plusieurs machines coopèrent afin de calculer une solution à un problème. Dans ce modèle, les machines sont représentées par les noeuds d'un graphe et ne peuvent communiquer qu'avec leurs voisins. Les communications se font de façon synchrones, sans bornes sur les capacités de calcul des processeurs ni sur la taille des messages qu'ils peuvent envoyer.

Dans ce modèle, le problème de coloriage de graphe entre autres a attiré beaucoup d'attention, et malgré de nombreux résultats, il reste encore un écart important entre la complexité du meilleur algorithme pour ce problème, et la meilleure borne inférieure.

Dans cette présentation, je vais présenter un nouveau problème, le coloriage de graphe avec des conflits, qui généralise le problème de coloriage classique. Nous verrons ensuite un algorithme qui améliore certains résultats existants pour le coloriage de graphe, et les généralise au problème de coloriage avec des conflits.

Les lundi 15 novembre et mardi 16 novembre 2016, les journées "Information and Complexity Day, Lyon 2016", organisé par Omar Fawzi et Graphes@Lyon, à l'ENS de Lyon.

Vendredi 4 novembre 2016 au LIP : Khang Le (LIP)

Title: Chromatic number of ISK4-free graphs

Abstract: A subdivision of a graph G is obtained by subdividing its edges into paths of arbitrary length (at least one). We denote by K_n the complete graph on n vertices. A graph is ISK4-free if it does not contain any subdivision of K_4 as an induced subgraph. We prove that the chromatic number of {ISK4, triangle}-free graphs is at most 3 and the chromatic number of ISK4-free graphs is at most 24, which improves the upper bound for the chromatic number of these classes provided by B. Lévêque, F. Maffray, and N. Trotignon (2012). We also discuss some related open questions.

Vendredi 16 décembre au LIP : Jean-Florent Raymond (LIRMM), salle de réunion équipe MC2, au LUG (LIP, Gerland)

Title: Deleting Immersions

Abstract: Suppose F is a finite family of graphs. We consider the following
problem, called F-Immersion Deletion: given a graph G and integer k,
decide whether the deletion of at most k edges of G can result in a
graph that does not contain any graph from F as an immersion. This
problem is a close relative of the F-Minor Deletion problem studied by
Fomin et al. [FOCS 2012], where one deletes vertices in order to remove
all minor models of graphs from F.

We prove that whenever all graphs from F are connected and at least one
graph of F is planar and subcubic, then the F-Immersion Deletion problem
admits a constant factor approximation and a linear kernel.
These results mirror those obtained by Fomin et al. on the F-Minor
Deletion problem, with some notable differences, though.

This is joint work with Archontia Giannopoulou, Michał Pilipczuk,
Dimitrios Thilikos, and Marcin Wrochna.
A preprint can be found at http://arxiv.org/abs/1609.07780.

Le vendredi 17 février 2017 salle de réunion équipe MC2, au LUG (LIP, Gerland) : Valentin Garnero (INRIA)

Title: (Méta)-noyaux constructifs et linéaires dans les graphes peu denses

    Dans cet exposé je vous présenterai les résultats obtenus au cours de ma thèse, laquelle traite de noyaux et de complexité paramétrée.
La complexité paramétrée est une branche de l'algorithmie qui analyse la complexité d'un problème en fonction de la taille des données n et d'un paramètre k (arbitraire). L'objectif est de pouvoir attaquer des problèmes difficiles (NPc) et de montrer que l’exposition combinatoire n'est fonction que du paramètre (et pas de la taille des données), cad, trouver des algorithmes en f(k)+p(n). L'extraction de noyau est une méthode qui permet d'obtenir des algorithmes avec un telle complexité. Il s'agit d'un pré-calcul (une réduction polynomiale) qui réduit la taille des données en temps polynomial, tout en garantissant que la taille du noyau (l'instance réduite) est bornée par une fonction du paramètre g(k). Il suffit de résoudre le problème dans le noyau, de n'importe quelle façon, pour obtenir un algorithme en f(g(k)) + p(n).
    La méthode de décomposition en régions [Alber, Fellows, Niedermeier] est un résultat majeur dans le domaine des noyaux. Elle a permis de construire de nombreux noyaux linaires pour des variantes de la Domination dans les graphes planaires. J'illustrerai cette méthode avec le cas de la Domination Rouge Bleu, qui consiste à trouver, dans un graphe bicoloré, un ensemble de sommets bleus tel que tous les sommets rouges sont à distance au plus 1 de la solution.
    Cette méthode a ensuite été généralisée par des méta-résultats [ex: Bodlaender, Fomin, Lokshtanov, Penninkx, Saurabh, Thilikos], qui prouve l'existence de noyaux (dans des graphes peu denses) pour tout problème vérifiant certaines conditions génériques. Je présenterai un de ses méta-résultats, qui se base sur la programmation dynamique et sur la décomposition en protrusion, et qui a le mérite d’être constructif.

Le vendredi 24 février 2017 au LIRIS en salle C5 : Valia Mitsou (LIRIS)

Titre : Choosability: a hard graph coloring problem

Résumé : Choosability, independently introduced by Vizing in 1976 and by Erdős, Rubin, and Taylor in 1979 is a well-studied graph-theoretic concept. We say that a graph G is k-choosable if for any assignment of lists of k colors on the verices of G we can color each vertex using a color from its list such that the coloring is proper. We will present a number of graph-theoretic observations and algorithmic results on the choosability problem and its generalization choosability deletion. This talk is based on recent work jointly done with Dániel Marx ("Double-exponential and triple-exponential bounds for choosability problems parameterized by treewidth"), which was presented at ICALP 2016.

Lundi 27 mars 2017 au LIRIS, salle C5: Mickaël Montassier (LIRMM)

Titre : Vertex partitions of graphs

Résumé : We present a survey on vertex partitions of graphs (especially, planar and/or sparse graphs) where each set of the partition induces a particular structure (for example, stable sets, matchings, forests,...).

Vendredi 7 avril 2017 au LIRIS, salle C5 du Nautibus : O-joung Kwon (Technische Universitat Berlin)

Title : Low rank-width colorings of graphs

Abstract : We introduce the concept of low rank-width colorings, generalizing the
notion of low tree-depth colorings introduced by Nesetril and Ossona de Mendez. We say that a class C of graphs admits low rank-width colorings if there exist functions N:N->N and Q:N->N such that for all integer p, every graph G in the class C can be vertex colored with at most N(p) colors such that the union of any i<= p color classes induces a subgraph of rank-width at most Q(i).

Graph classes admitting low rank-width colorings strictly generalize graph classes admitting low tree-depth colorings and graph classes of bounded rank-width. We prove that for every graph class C
of bounded expansion and every positive integer r, the class {G^r, G in C} of r-th powers of graphs from C, as well as the classes of unit interval graphs and bipartite permutation graphs admit low rank-width colorings. All of these classes have unbounded rank-width and do not admit low tree-depth colorings. We also show that the classes of interval graphs and permutation graphs do not admit low rank-width colorings. As interesting side properties, we prove that every graph class admitting low rank-width colorings has the Erdos-Hajnal property and is chi-bounded.

Vendredi 28 avril 2017 au LIRIS, salle TD11 (Nautibus) : Claire Pennarun (LaBRI)

Title : Power domination in triangulations

Abstract: Power domination in graphs emerged from the problem of monitoring
an electrical system by placing as few measurement devices in the system
as possible. Given a set S of vertices of a graph, a set M of vertices is built
as follows: at first, M = N [S], and then iteratively a vertex v is added to
M if v has a neighbor u in M such that v is the only neighbor of u not
in M. Such a set S is said to be power dominating for a graph G if all
vertices of G are in M at the end of the process. The power domination
number of a graph is the minimum size of a power dominating set. In this
talk, we present some results concerning power domination in triangulations,
and we in particular prove that any maximal planar graph of order n ≥ 6
admits a power dominating set of size at most (n−2)/4.

Le lundi 15 mai 2017 au LUG, salle de réunion : Ross Khang (Radboud University Nijmegen)

Title: Distance colourings and one forbidden cycle length

Abstract: Graph powers arise naturally in the study of, for example, efficient network communication. Some basic problems have remained stubbornly open for a long time. I will first discuss previous work on the chromatic number of graph powers, for graphs of maximum degree d,
often taking d very large. This is related to conjectures of Bollobás and of Erdős and Nešetřil from the 1980s. Then I will discuss the imposition of a girth or cycle length restriction, in relation to a problem of Alon and Mohar. We have obtained several asymptotically sharp results along these lines, which extends a seminal work of Johansson to distance colourings. This is joint work with Francois Pirot.

Vendredi 9 juin 2017 au LIRIS, Nautibus (salle à venir) : Vincent Despré (LIP)

Titre: A Routing Algorithm for Delaunay Triangulations.

Abstract Delaunay Triangulations are graphs defined on sets of points in the plane. They are very classical since their construction is natural and they have strong geometric properties. One of the more classical study about those triangulations is the calculation of the worst possible stretch for a pair of points . The stretch of a pair is defined by the worst length of a shortest path between those points divided by the Euclidian distance between them. Computing this shortest path is generally considered as efficient but it is not the case for very big triangulations. It becomes interesting to only consider local information at each step while routing from one vertex to the other. Our work consists in designing an algorithm with this restriction that outputs a path with a reasonable stretch.

Vendredi 22 septembre 2017, à 10h, salle de réunion équipe MC2, au LUG :Jean-Florent Raymond (LIRMM)

Title: Separators & Expansion

Abstract: The concept of bounded expansion has been introduced by Nešetřil and
Ossona de Mendez as a generalization of several known notions of
sparsity: being planar, excluding a fixed minor, having bounded degree,
and many more. Several algorithmic problems that are known to
be computationally hard in general turn out to be solvable in polynomial
time when the inputs are taken in a class of bounded expansion fixed in
advance.

On the other hand, classes of graphs with (balanced) sublinear
separators are extensively used in the design of algorithms and enjoy
nice structural properties. An example of graphs with sublinear
separators is the class of planar graphs, by a classic result of Lipton
and Tarjan.

In this talk I will discuss the connections between these two notions.
Let C be a subgraph-closed class of graphs. Dvořák and Norin proved that
graphs in C have sublinear balanced separators iff they have polynomial
expansion. They conjectured that if the balanced separators in C
have size O(n^{1−δ}) (for some 0 < δ ≤ 1), then the expansion in C is
O(k^{c/δ}), for some constant c. We prove this conjecture. This is joint
work with Louis Esperet.

Vendredi 10 novembre 2017, à 10h au LIRIS, salle C1 du Nautibus : Lucas Pastor (G-SCOP, Grenoble)

Title: Colouring squares of claw-free graphs

Abstract: Let G be a claw-free graph. We consider the square G^2 of G, which is the
graph formed from G by the addition of edges between those pairs of vertices
connected by some two-edge path in G, and consider proper colourings of G^2. In
particular, we relate the chromatic number of G^2 to the clique number of G.
We prove that there is an absolute constant epsilon > 0 such that the chromatic
number of G^2 is at most (2- epsilon)χ(G)^2 for any claw-free graph G. Our main
theorem extends a result of Molloy and Reed who first gave a positive answer to
a conjecture of Erdős and Nešetřil.

Joint-work with Rémi de Joannis de Verclos and Ross Kang.