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.


Emplois - Stages

Groupe

GT Graphes et Optimisation

Historique

edit SideBar