2017 - 2018


Vendredi 1 septembre 2017 - ​Un algorithme optimal pour ​Cycle Hamiltonien paramétré par la largeur de clique​ - Benjamin Bergougnoux (LIMOS, Clermont-Ferrand).
La largeur de clique (clique-width) est plus générale que la largeur arborescente (tree-width)​: elle est bornée dans plus de classes de graphes​,​​ dont certaines classes de graphes denses. Malgré cette généralité, elle permet de résoudre en temps FPT tous les problèmes exprimables en logique monadique du premier ordre.

D'un point de vu pratique son intérêt est limité car on ne sait toujours pas la calculer "rapidement". ​​Elle reste intéressante car elle permet d'étudier la complexité des problèmes NP-difficiles dans les graphes denses.

Je vais présenter un algorithme résolvant Cycle Hamiltonien en temps n^O(k). Cet algorithme est optimal sous ETH (Exponential Time Hypothesis) et répond à une question ouverte soulevée par Fomin et al. (SIAM. J. Computing, 2014).

Notre algorithme bat l'algorithme naïf dont le temps d'exécution est n^O(k²). Il s'appuie sur une relation d’équivalence qui se base sur un résultat amusant concernant l'existence d'une marche Eulérienne (alternant deux types d'arêtes) dans les multigraphes.

Travail en collaboration avec Mamadou M. Kanté et O-joung Kwon.

Vendredi 8 septembre 2017 11h - Large Induced 2-degenerate Subgraphs of Triangle-free Planar Graphs - Tom Kelly (University of Waterloo, Canada).
A graph is k-degenerate if every subgraph has minimum degree at most k. Studying lower bounds on the size of induced subgraphs of low degeneracy has attracted a lot of attention. In this talk we will discuss lower bounding the size of a maximum induced 2-degenerate subgraph of a triangle-free planar graph. We prove that if G is a connected triangle-free planar graph with n vertices and m edges, then G contains an induced 2-degenerate subgraph on at least four fifths of its vertices. We also prove that if G is a triangle-free planar graph on n vertices with at most n_3 vertices of degree at most three, then G contains an induced 2-degenerate subgraph on at least 7n/8 - 28n_3 vertices. Joint work with Zdenek Dvorak.

Jeudi 14 septembre 2017 10h - Domination in structured tournaments - Nicolas Bousquet (G-SCOP, Grenoble).
Salle 76 !
There exist tournaments, such as random tournaments, for which the domination number is arbitrarily large. One can naturally ask what happens if we add some structure on the tournament, for instance if the tournament can be "covered" using a bounded number of partial orders. Alon et al. showed that k-majority tournaments have bounded domination number. Gyarfas and Palvolgyi conjectured that the following is true : If a tournament admits a partition of its arc set into k quasi orders, then its domination number is bounded in terms of k. We provide a short proof that the following more general conjecture of Erdos, Sands, Sauer and Woodrow: If the arcs of a tournament T are colored with k colors, there exist a set X of at most g(k) vertices such that for every vertex v of T, there is a monochromatic path from X to v.

(joint work with William Lochet and Stéphan Thomassé)

Vendredi 15 septembre 2017 - Turan problems for sets of binary vectors - Peter Nelson (University of Waterloo, Canada).
Given a fixed set N of vectors in GF(2)^k, we study, for large n, the maximum size of a set M of vectors in GF(2)^n that does not contain a linear copy of N. We argue that such problems closely resemble analogous extremal problems for H-free graphs, and discuss a surprising matroidal analogue of chromatic number that supports this view.

Vendredi 22 septembre 2017 - On the List Coloring Version of Reed's Conjecture - Michelle Delcourt (University of Birmingham, Royaume-Uni).
Reed conjectured in 1998 the chromatic number of a graph should be at most halfway between clique number (trivial lower bound) and maximum degree plus one (trivial upper bound); Reed proved it is at most some convex combination of these quantities. Last year, Bonamy, Perrett, and Postle proved for large enough maximum degree, a fraction of 1/26 away from the upper bound holds. Using new techniques, we show the list-coloring version holds; for large enough maximum degree, a fraction of 1/13 suffices for list chromatic number. Thus, 1/13 suffices for ordinary chromatic number. This is joint work with Luke Postle.

Mardi 26 Septembre 2017 14h30 - Correspondence Coloring: A Survey - Luke Postle (University of Waterloo, Canada).
Recently introduced in 2015, correspondence coloring is a generalization of list coloring, which is a generalization of coloring introduced in the 1970s. In correspondence coloring, vertices are given lists of colors as in list coloring; however, the meaning of color is only local rather than global. In this talk, we survey what is known about correspondence coloring, how it has been used to prove results for list coloring that were not previously known, as well as some open questions.

Vendredi 13 octobre 2017 - Orientations of sparse uniform hypergraphs - William Lochet (ÉNS de Lyon et Université de Nice Sophia Antipolis).
A classical result in graph theory states that any graph G can be oriented in a way that the indegree and the outdegree of each vertex differ by at most one. In 2011 Cairo, West and Yuster tried to generalise this result to r-uniform hypergraphs, where an orientation of an hyperedge is a total ordering of its element. They conjectured an existence result of such orientations for sparse hypergraphs, of which we present a proof. The proof relies on two probabilistic tools: Moser's entropy compression method and the Lopsided Lovasz Local Lemma.

Vendredi 13 octobre 2017 15h - How to properly distinguish neighbours randomly choosing edge colours from prescribed lists? - Jakub Przybyło (AGH University, Cracovie, Pologne).
Let G=(V,E) be a graph. Consider an edge colouring c:E-> C. For a given vertex v in V, by E(v) we denote the set of all edges incident with v in G, while the set of colours associated to these under c is denoted as: Sc(v)={c(e):e in E(v)} The colouring c is called adjacent vertex distinguishing if it is proper and Sc(u) <> Sc(v) for every edge uv in E. It exists if only G contains no isolated edges. The least number of colours in C necessary to provide such a colouring is then denoted by chi'_a(G) and called the adjacent vertex distinguishing edge chromatic number of G. Obviously, chi'_a(G) >= chi'(G) >= Delta, where Delta is the maximum degree of G, while it was conjectured that chi'_a(G) <= Delta+2 for every connected graph G of order at least three different from the cycle C5. Hatami proved the postulated upper bound up to an additive constant by showing that chi'_a(G) <= Delta+300 for every graph G with no isolated edges and with maximum degree Delta>10^20.
Suppose now that every edge e in E is endowed with a list of available colours L_e. The adjacent vertex distinguishing edge choice number of a graph G (without isolated edges) is defined as the least k so that for every set of lists of size k associated to the edges of G we are able to choose colours from the respective lists to obtain an adjacent vertex distinguishing edge colouring of G. We denote it by ch'_a(G). Analogously as above, ch'_a(G) >= ch'(G), while the best (to my knowledge) general result on the classical edge choosability implies that ch'(G)=Delta+O(Delta^1/2 log^4(Delta)). Extending the thesis of this, a four-stage probabilistic argument granting ch'_a(G)=Delta+O(Delta^1/2 log^4(Delta)) for the class of all graphs without isolated edges shall be presented during the talk.
This is joint work with Jakub Kwa ́sny.

Vendredi 20 octobre 2017 - Sur le plus petit ensemble de transitions nécessaire pour connecter un graphe - 1/2 - Thomas Bellitto (LaBRI).
Une transition dans un graphe est une paire d'arêtes adjacentes, qui peuvent donc être empruntées l'une à la suite de l'autre lors d'une marche dans le graphe. Par exemple, la marche u→v→w utilise les arêtes {u,v} et {v,w} et la transition {{u,v},{ v,w}}. Un graphe à transitions interdites est un triplet (V,E,T) où T est l'ensemble des transitions autorisées. On dit qu'une marche sur un graphe est T-compatible si elle n'utilise que des transitions de T et on dit que le graphe est T-connexe s'il existe une marche T-compatible entre toute paire de sommets de V. Le problème qui nous intéresse dans cet exposé est, étant donné un graphe à transitions interdites G=(V,E,T) T-connexe, de trouver le plus petit sous-ensemble T' de T tel que G est T'-connexe. Nous étudierons tout particulièrement le cas où T contient toutes les paires d'arêtes adjacentes de E.

Mardi 24 octobre 2017 - Sur le plus petit ensemble de transitions nécessaire pour connecter un graphe - 2/2 - Thomas Bellitto (LaBRI).
Une transition dans un graphe est une paire d'arêtes adjacentes, qui peuvent donc être empruntées l'une à la suite de l'autre lors d'une marche dans le graphe. Par exemple, la marche u→v→w utilise les arêtes {u,v} et {v,w} et la transition {{u,v},{ v,w}}. Un graphe à transitions interdites est un triplet (V,E,T) où T est l'ensemble des transitions autorisées. On dit qu'une marche sur un graphe est T-compatible si elle n'utilise que des transitions de T et on dit que le graphe est T-connexe s'il existe une marche T-compatible entre toute paire de sommets de V. Le problème qui nous intéresse dans cet exposé est, étant donné un graphe à transitions interdites G=(V,E,T) T-connexe, de trouver le plus petit sous-ensemble T' de T tel que G est T'-connexe. Nous étudierons tout particulièrement le cas où T contient toutes les paires d'arêtes adjacentes de E.

Vendredi 27 octobre 2017 - Frankl's conjecture for large families - Ilan Karpas (Hebrew University of Jerusalem) .
A family F of subsets of [n] is called union-closed, if for any two sets A and B in F, A ∪ B is also in F. A famous conjecture of Frankl from 1979 states that for any union-closed family F ≠ ∅ of subsets of [n], there is some element i ∈ [n] that occurs in at least half of the members of F.
We show that the conjecture holds if F is a family of subsets of [n], and |F| ≥ (1/2 - c)2^n, for some absolute constant c>0. This improves a result of Eccles from 2013, who proved that the conjecture holds for |F| ≥ (2/3 - 1/104)2^n.
We use methods from boolean analysis to prove the claim, as well as a structural theorem about the upper shadow of union-closed families. We end the talk by discussing some new conjectures regarding union-closed families.

Vendredi 3 novembre - Pas de GT cause vacances.

Vendredi 17 novembre - Pas de GT cause JGA.

Vendredi 24 novembre 2017 - Homomorphisms of sparse signed graphs - Reza Naserasr (IRIF, Paris).
The notion of homomorphism of graphs has recently been extended to homomorphism of signed graphs in a joint work with E. Rollova and E. Sopena. A key interest in this extension, among many, is that it provides a more intuitive and, at the same time, stronger connection with the notion of minor of (signed) graphs.
In this talk I will present some results from a joint work with C. Charpentier and E. Sopena concerning homomorphisms of sparse signed graphs. Two main results to be mentioned:
Theorem. For any graph G of maximum average degree less than 8/3 and any signature Sigma of G, the signed graph (G,Sigma) maps to (K_4,e). Furthermore, 8/3 is the best possible value here.
As a bipartite analogue of Jaeger-Zhang Conjecture, we propose the following
Conjecture. Every signed bipartite planar graph of unbalanced girth at least 4k-2 maps to the unbalanced cycle of length 2k.
In support of this conjecture, we prove that the claim would hold for signed bipartite planar graphs of unbalanced girth at least 8k.

Vendredi 24 novembre 2017 15h - Graph classes defined by excluding Truemper Configurations - Nicolas Trotignon (ÉNS de Lyon, Lyon).
Tremper configurations are simple structures : prisms, thetas, pyramids and wheel. A prism is a graph made of two disjoint triangles that are matched by three disjoint paths. A theta is a graph made of two disjoint vertices that are linked by three disjoint paths. A pyramid is a graph made of a vertex and triangle that are linked by three disjoint paths. A wheel is a chordless cycle together with a vertex disjoint from it, and with at least three neighbors in it. In this abstract we omitted technical requirements on the lengths of the paths and cycles.

Truemper configuration play an important in role in several theorems. For instance, they appear in an old characterisation of graph with no cycle through three prescribed vertices (due to Watkins and Mesner). They appear in a theorem of Truemper about signing edges of a graph in such way that several constraints on the parity of cycles are satisfied. And they play an important role in many recent decomposition theorems in structural graph theory (perfect graphs, even-hole-free graphs, claw-free graphs, bull-free graphs, and some others).

The talk will focus on this last aspect. I will explain why Truemper Configuration are important in decomposition theorems. Then I will present a project about systematically studying the classes of graph where Truemper configuration are excluded.

Joint work with Marko Radovanovic and Kristina Vuskovic.

Vendredi 1er décembre 2017 10h salle de conférence (IMB) - Soutenance de thèse "Geometric Distance Graphs, Lattices and Polytopes" - Philippe Moustrou (LaBRI).

Vendredi 1er décembre 2017 - Largeur de clique : Majorations polynomiales en termes de largeur arborescente. - Bruno Courcelle (LaBRI).
Dans le cas le plus général, la largeur de clique est exponentielle en la largeur arborescente. Mais pour des classes de graphes "peu denses", notamment celles étudiées par Nesetril et Ossona de Mendez, on a des majorations polynomiales et même souvent linéaires (cas de l'expansion bornée). Mon exposé examine ces majorations. Un algorithme unique (le même pour tous les types de graphes) convertit une décomposition arborescente en terme relatif à la largeur de clique. Les décompositions arborescentes sont fournies sous la forme d'un arbre "normal" analogue à un arbre d'exploration en profondeur.

Mardi 5 décembre 2017 11h - Séminaire commun avec MF - La coloration de graphe dans le modèle LOCAL - Partie I - Cyril Gavoille (LaBRI).
L'objectif de cette série d'exposés est de faire découvrir un résultat aussi élégant que surprenant du calcul distribué, à savoir la 3-coloration des n-cycles en temps log*(n). On démontrera l'optimalité de ce résultat ainsi que ces généralisations au cas des graphes arbitraires. Partie I: - Le modèle LOCAL - Le problème de la coloration - Coloration des 1-orientations en 6 couleurs - De 6 à 3 couleurs - Cas des graphes arbitraires


Emplois - Stages

Groupe

GT Graphes et Optimisation

Historique

edit SideBar