m
• E

F Nous contacter

0

Multi angle

H 1 Induced cycles and coloring

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

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 graphesOrganisateurs de la rencontre : Kreutzer, Stephan ; Paul, Christophe ; Trotignon, Nicolas ; Wollan, PaulDates : 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

Bibliographie

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

0
Z