En poursuivant votre navigation sur ce site, vous acceptez l'utilisation d'un simple cookie d'identification. Aucune autre exploitation n'est faite de ce cookie. OK
1

Induced cycles and coloring

Bookmarks Report an error
Multi angle
Authors : Chudnovsky, Maria (Author of the conference)
CIRM (Publisher )

Loading the player...

Abstract : 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.

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

    Information on the Video

    Film maker : Hennenfent, Guillaume
    Language : English
    Available date : 04/02/15
    Conference Date : 20/01/15
    Subseries : Research talks
    arXiv category : Combinatorics
    Mathematical Area(s) : Combinatorics
    Format : MP4 (.mp4) - HD
    Video Time : 00:42:11
    Targeted Audience : Researchers
    Download : https://videos.cirm-math.fr/2015-01-20_Chudnovsky.mp4

Information on the Event

Event Title : International workshop on graph decomposition / Rencontre internationale sur les méthodes de décomposition de graphes
Event Organizers : Kreutzer, Stephan ; Paul, Christophe ; Trotignon, Nicolas ; Wollan, Paul
Dates : 19/01/15 - 23/01/15
Event Year : 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

Bibliography



Bookmarks Report an error