Multi angle

H 1 Induced cycles and coloring

Auteurs : Chudnovsky, Maria (Auteur de la Conférence)
CIRM (Editeur )

    Loading the player...

    Résumé : A hole in a graph is an induced cycle of length at least four, and an odd hole is a hole of odd length. A famous conjecture of A. Gyárfás [1] from 1985 asserts:
    Conjecture 1: For all integers $k,l$ there exists $n(k,l)$ such that every graph $G$ with no clique of carnality more than $k$ and no odd hole of length more than $l$ has chromatic number at most $n(k,l)$.

    In other words, the conjecture states that the family of graphs with no long odd holes is $\chi$-bounded. Little progress was made on this problem until recently Scott and Seymour proved that Conjecture 1 is true for all pairs $(k,l)$ when $l=3$ (thus excluding all odd holes guarantees $\chi$-boundedness) [3].
    No other cases have been settled, and here we focus on the case $k=2$. We resolve the first open case, when $k=2$ and $l=5$, proving that
    Theorem 1. Every graph with no triangle and no odd hole of length $>5$ is $82200$-colorable.

    Conjecture 1 has a number of other interesting special cases that still remain open; for instance
    * Conjecture: For all $l$ every triangle-free graph $G$ with sufficiently large chromatic number has an odd hole of length more than $l$;
    * Conjecture: For all $k,l$ every graph with no clique of size more than $k$ and sufficiently large chromatic number has a hole of length more than $l$.

    We prove both these statements with the additional assumption that $G$ contains no $5$-hole. (The latter one was proved, but not published, by Scott earlier, improving on [2]). All the proofs follows a similar outline. We start with a leveling of a graph with high chromatic number, that is a classification of the vertices by their distance from a fixed root. Then the graph undergoes several rounds of "trimming" that allows us to focus on a subgraph $M$ with high chromatic number that is, in some sense, minimal. We also ensure that certain pairs of vertices with a neighbor in $M$ can be joined by a path whose interior is anticomplete to $M$. It is now enough to find two long paths between some such pair of vertices, both with interior in $M$ and of lengths of different parity, to obtain a long odd hole.

    Codes MSC :
    05C15 - Coloring of graphs and hypergraphs
    05C85 - Graph algorithms

      Informations sur la Vidéo

      Langue : Anglais
      Date de publication : 04/02/15
      Date de captation : 20/01/15
      Sous collection : Research talks
      Format : quicktime ; audio/x-aac
      arXiv category : Combinatorics
      Domaine : Combinatorics
      Durée : 00:42:11
      Audience : Chercheurs ; Doctorants , Post - Doctorants
      Download : https://videos.cirm-math.fr/2015-01-20_Chudnovsky.mp4

    Informations sur la rencontre

    Nom de la rencontre : International workshop on graph decomposition / Rencontre internationale sur les méthodes de décomposition de graphes
    Organisateurs de la rencontre : Kreutzer, Stephan ; Paul, Christophe ; Trotignon, Nicolas ; Wollan, Paul
    Dates : 19/01/15 - 23/01/15
    Année de la rencontre : 2015

    Citation Data

    DOI : 10.24350/CIRM.V.18673503
    Cite this video as: Chudnovsky, Maria (2015). Induced cycles and coloring. CIRM. Audiovisual resource. doi:10.24350/CIRM.V.18673503
    URI : http://dx.doi.org/10.24350/CIRM.V.18673503


    1. [1] Gyárfás, A. (1987). Problems from the world surrounding perfect graphs. Zastosowania Matematyki, 19(3-4), 413-441 - https://www.zbmath.org/?q=an:0718.05041

    2. [2] Scott, A. (1999). Induced cycles and chromatic number. Journal of Combinatorial Theory. Series B, 76(2), 150-154 - http://dx.doi.org/10.1006/jctb.1998.1894

    3. [3] Scott, A., & Seymour, P. (2014). Colouring graphs with no odd holes - http://arxiv.org/abs/1410.4118

Titres de périodiques et e-books électroniques (Depuis le CIRM)

Ressources Electroniques

Books & Print journals

Recherche avancée