Français
Colouring graphs with no odd holes, and other stories
Post-edited
Authors : Seymour, Paul D. (Author of the conference)
CIRM (Publisher )
05C15 - Coloring of graphs and hypergraphs
05C35 - Extremal problems (graph theory)
05C85 - Graph algorithms
CIRM (Publisher )
Loading the player...
|
| Gyarfas' conjecture on odd holes proof of Gyarfas' conjecture levelling spine parent rule cograph of jumps Gyarfas' conjecture on long holes tree-decomposition uncle trees |
Abstract :
The chromatic number $\chi(G)$ of a graph $G$ is always at least the size of its largest clique (denoted by $\omega(G)$), and there are graphs $G$ with $\omega(G)=2$ and $\chi(G)$ arbitrarily large.
On the other hand, the perfect graph theorem asserts that if neither $G$ nor its complement has an odd hole, then $\chi(G)=\omega(G)$ . (A "hole" is an induced cycle of length at least four, and "odd holes" are holes of odd length.) What happens in between?
With Alex Scott, we recently proved the following, a 1985 conjecture of Gyárfás:
For graphs $G$ with no odd hole, $\chi(G)$ is bounded by a function of $\omega(G)$.
Gyárfás also made the stronger conjecture that for every integer $k$ and for all graphs $G$ with no odd hole of length more than $k$, $\chi(G)$ is bounded by a function of $k$ and $\omega(G)=2$. This is far from settled, and indeed the following much weaker statement is not settled: for every integer $k$, every triangle-free graph with no hole of length at least $k$ has chromatic number bounded by a function of $k$. We give a partial result towards the latter:
For all $k$, every triangle-free graph with no hole of length at least $k$ admits a tree-decomposition into bags with chromatic number bounded by a function of $k$.
Both results have quite pretty proofs, which will more-or-less be given in full.
MSC Codes : On the other hand, the perfect graph theorem asserts that if neither $G$ nor its complement has an odd hole, then $\chi(G)=\omega(G)$ . (A "hole" is an induced cycle of length at least four, and "odd holes" are holes of odd length.) What happens in between?
With Alex Scott, we recently proved the following, a 1985 conjecture of Gyárfás:
For graphs $G$ with no odd hole, $\chi(G)$ is bounded by a function of $\omega(G)$.
Gyárfás also made the stronger conjecture that for every integer $k$ and for all graphs $G$ with no odd hole of length more than $k$, $\chi(G)$ is bounded by a function of $k$ and $\omega(G)=2$. This is far from settled, and indeed the following much weaker statement is not settled: for every integer $k$, every triangle-free graph with no hole of length at least $k$ has chromatic number bounded by a function of $k$. We give a partial result towards the latter:
For all $k$, every triangle-free graph with no hole of length at least $k$ admits a tree-decomposition into bags with chromatic number bounded by a function of $k$.
Both results have quite pretty proofs, which will more-or-less be given in full.
05C15 - Coloring of graphs and hypergraphs
05C35 - Extremal problems (graph theory)
05C85 - Graph algorithms
|
Information on the Video
Film maker : Hennenfent, GuillaumeLanguage : English Available date : 04/02/15 Conference Date : 21/01/15 Subseries : Research talks arXiv category : Combinatorics Mathematical Area(s) : Combinatorics Format : QuickTime (.mov) Video Time : 00:55:58 Targeted Audience : Researchers Download : https://videos.cirm-math.fr/2015-01-21_Seymour.mp4 
|
Information on the Event
Event Title : International workshop on graph decomposition / Rencontre internationale sur les méthodes de décomposition de graphesEvent 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.18671503Cite this video as: Seymour, Paul D. (2015). Colouring graphs with no odd holes, and other stories. CIRM. Audiovisual resource. doi:10.24350/CIRM.V.18671503 URI : http://dx.doi.org/10.24350/CIRM.V.18671503 |
Bibliography
- Chudnovsky, M., Robertson, N., Seymour, P. & Thomas, R. (2006). The strong perfect graph theorem. Annals of Mathematics. Second Series, 164(1), 51-229 - http://dx.doi.org/10.4007/annals.2006.164.51
- Chudnovsky, M., Scott, A. & Seymour, P. (2014). Three steps towards Gyarfas' conjecture.
- 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
- Scott, A., & Seymour, P. (2014). Colouring graphs with no odd holes
- 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
