Induced subgraphs of graphs with large chromatic number. VII: Gyárfás’ complementation conjecture. (English) Zbl 1436.05076
Summary: A class of graphs is \(\chi\)-bounded if there is a function \(f\) such that \(\chi(G) \leq f(\omega(G))\) for every induced subgraph \(G\) of every graph in the class, where \(\chi, \omega\) denote the chromatic number and clique number of \(G\) respectively. A. Gyárfás [Zastosow. Mat. 19, No. 3–4, 413–441 (1987; Zbl 0718.05041)] conjectured that for every \(c\), if \(\mathcal{C}\) is a class of graphs such that \(\chi(G) \leq \omega(G) + c\) for every induced subgraph \(G\) of every graph in the class, then the class of complements of members of \(\mathcal{C}\) is \(\chi \)-bounded. We prove this conjecture. Indeed, more generally, a class of graphs is \(\chi \)-bounded if it has the property that no graph in the class has \(c + 1\) odd holes, pairwise disjoint and with no edges between them. The main tool is a lemma that if \(C\) is a shortest odd hole in a graph, and \(X\) is the set of vertices with at least five neighbours in \(V(C)\), then there is a three-vertex set that dominates \(X\).
For Part VI see [the authors, “Induced subgraphs of graphs with large chromatic number. VI. Banana trees”, Preprint, arXiv:1701.05597].
For Part VI see [the authors, “Induced subgraphs of graphs with large chromatic number. VI. Banana trees”, Preprint, arXiv:1701.05597].
MSC:
05C60 | Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) |
05C15 | Coloring of graphs and hypergraphs |
05C17 | Perfect graphs |
Citations:
Zbl 0718.05041References:
[1] | Cames van Batenburg, W.; Esperet, L.; Müller, T., Coloring pseudo-disks and Jordan curves · Zbl 1368.05058 |
[2] | Chudnovsky, M.; Cornuéjols, G.; Liu, X.; Vušković, K.; Seymour, P., Recognizing Berge graphs, Combinatorica, 25, 143-186 (2005) · Zbl 1089.05027 |
[3] | Esperet, L.; Gonçalves, D.; Labourel, A., Coloring non-crossing strings, Electron. J. Combin., 23 (2016), #P4.4 · Zbl 1351.05073 |
[4] | Gyárfás, A., Problems from the world surrounding perfect graphs, (Proceedings of the International Conference on Combinatorial Analysis and Its Applications. Proceedings of the International Conference on Combinatorial Analysis and Its Applications, Pokrzywna, 1985. Proceedings of the International Conference on Combinatorial Analysis and Its Applications. Proceedings of the International Conference on Combinatorial Analysis and Its Applications, Pokrzywna, 1985, Zastos. Mat., vol. 19 (1987)), 413-441 · Zbl 0718.05041 |
[5] | Gyárfás, A.; Li, Z.; Machado, R.; Sebő, A.; Thomassé, S.; Trotignon, N., Complements of nearly perfect graphs, J. Comb., 4, 299-310 (2013) · Zbl 1275.05024 |
[6] | Lovász, L., Normal hypergraphs and the perfect graph conjecture, Discrete Math., 2, 253-267 (1972) · Zbl 0239.05111 |
[7] | Scott, A.; Seymour, P., Induced subgraphs of graphs with large chromatic number. I. Odd holes, J. Combin. Theory Ser. B, 121, 68-84 (2016) · Zbl 1412.05076 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.