χ-bounded

In graph theory, a $\chi$ -bounded family ${\mathcal {F}}$ of graphs is one for which there is some function $f$ such that, for every integer $t$ the graphs in ${\mathcal {F}}$ with $t=\omega (G)$ (clique number) can be colored with at most $f(t)$ colors. The function $f(t)$ is called a $\chi$ -binding function for ${\mathcal {F}}$ . These concepts and their notations were formulated by András Gyárfás.^[1] The use of the Greek letter chi in the term $\chi$ -bounded is based on the fact that the chromatic number of a graph $G$ is commonly denoted $\chi (G)$ . An overview of the area can be found in a survey of Alex Scott and Paul Seymour.^[2]

Nontriviality

It is not true that the family of all graphs is $\chi$ -bounded. As Descartes (1947), Zykov (1949) and Mycielski (1955) showed, there exist triangle-free graphs of arbitrarily large chromatic number,^[3]^[4]^[5] so for these graphs it is not possible to define a finite value of $f(2)$ . Thus, $\chi$ -boundedness is a nontrivial concept, true for some graph families and false for others.^[6]

Specific classes

Every class of graphs of bounded chromatic number is (trivially) $\chi$ -bounded, with $f(t)$ equal to the bound on the chromatic number. This includes, for instance, the planar graphs, the bipartite graphs, and the graphs of bounded degeneracy. Complementarily, the graphs in which the independence number is bounded are also $\chi$ -bounded, as Ramsey's theorem implies that they have large cliques.

Vizing's theorem can be interpreted as stating that the line graphs are $\chi$ -bounded, with $f(t)=t+1$ .^[7]^[8] The claw-free graphs more generally are also $\chi$ -bounded with $f(t)\leq t^{2}$ . This can be seen by using Ramsey's theorem to show that, in these graphs, a vertex with many neighbors must be part of a large clique. This bound is nearly tight in the worst case, but connected claw-free graphs that include three mutually-nonadjacent vertices have even smaller chromatic number, $f(t)=2t$ .^[7]

Other $\chi$ -bounded graph families include:

The perfect graphs, with $f(t)=t$
The graphs of boxicity two^[9], which is the intersection graphs of axis-parallel rectangles, with $f(t)\in O(t\log(t))$ (big O notation)^[10]
The graphs of bounded clique-width^[11]
The intersection graphs of scaled and translated copies of any compact convex shape in the plane^[12]
The polygon-circle graphs, with $f(t)=2^{t}$
The circle graphs, with $f(t)=2t\log _{2}t+2\log _{2}\log _{2}t+10t$ ^[13] and (generalizing circle graphs) the "outerstring graphs", intersection graphs of bounded curves in the plane that all touch the unbounded face of the arrangement of the curves^[14]
The outerstring graph is an intersection graph of curves that lie in a common half-plane and have one endpoint on the boundary of that half-plane^[15]
The intersection graphs of curves that cross a fixed curve between 1 and $n\in \mathbb {N}$ times^[16]
The even-hole-free graphs, with $f(t)=2t$ , as every such graph has a vertex whose neighborhood is the union of two cliques^[17]

However, although intersection graphs of convex shapes, circle graphs, and outerstring graphs are all special cases of string graphs, the string graphs themselves are not $\chi$ -bounded. They include as a special case the intersection graphs of line segments, which are also not $\chi$ -bounded.^[6]

Unsolved problems

Unsolved problem in mathematics:

Are all tree-free graph classes

\chi

-bounded?

(more unsolved problems in mathematics)

According to the Gyárfás–Sumner conjecture, for every tree $T$ , the graphs that do not contain $T$ as an induced subgraph are $\chi$ -bounded. For instance, this would include the case of claw-free graphs, as a claw is a special kind of tree. However, the conjecture is known to be true only for certain special trees, including paths^[1] and radius-two trees.^[18]

A $\chi$ -bounded class of graphs is polynomially $\chi$ -bounded if it has a $\chi$ -binding function $f(t)$ that grows at most polynomially as a function of $t$ . As every $n$ -vertex graph $G$ contains an independent set with cardinality at least $n/\chi (G)$ , all polynomially $\chi$ -bounded classes have the Erdős–Hajnal property. Another problem on $\chi$ -boundedness was posed by Louis Esperet, who asked whether every hereditary class of graphs that is $\chi$ -bounded is also polynomially $\chi$ -bounded.^[8] A strong counterexample to Esperet's conjecture was announced in 2022 by Briański, Davies, and Walczak, who proved that there exist $\chi$ -bounded hereditary classes whose function $f(t)$ can be chosen arbitrarily as long as it grows more quickly than a certain cubic polynomial.^[19]

References

^ ^a ^b Gyárfás, A. (1987), "Problems from the world surrounding perfect graphs" (PDF), Proceedings of the International Conference on Combinatorial Analysis and its Applications (Pokrzywna, 1985), Zastosowania Matematyki, 19 (3–4): 413–441 (1988), MR 0951359
^ Scott, Alex; Seymour, Paul (2020), "A survey of $\chi$ -boundedness", Journal of Graph Theory, 95 (3): 473–504, MR 4174126
^ Descartes, Blanche (1947), "A three colour problem", Eureka, 21
^ Zykov, A. A. (1949), "О некоторых свойствах линейных комплексов" [On some properties of linear complexes], Mat. Sbornik, New Series (in Russian), 24 (66): 163–188, MR 0035428. Translated into English in Amer. Math. Soc. Translation, 1952, MR0051516. As cited by Pawlik et al. (2014)
^ Mycielski, Jan (1955), "Sur le coloriage des graphs", Colloq. Math. (in French), 3 (2): 161–162, doi:10.4064/cm-3-2-161-162, MR 0069494
^ ^a ^b Pawlik, Arkadiusz; Kozik, Jakub; Krawczyk, Tomasz; Lasoń, Michał; Micek, Piotr; Trotter, William T.; Walczak, Bartosz (2014), "Triangle-free intersection graphs of line segments with large chromatic number", Journal of Combinatorial Theory, Series B, 105: 6–10, arXiv:1209.1595, doi:10.1016/j.jctb.2013.11.001, MR 3171778, S2CID 9705484
^ ^a ^b Chudnovsky, Maria; Seymour, Paul (2010), "Claw-free graphs VI. Colouring", Journal of Combinatorial Theory, Series B, 100 (6): 560–572, doi:10.1016/j.jctb.2010.04.005, MR 2718677
^ ^a ^b Karthick, T.; Maffray, Frédéric (2016), "Vizing bound for the chromatic number on some graph classes", Graphs and Combinatorics, 32 (4): 1447–1460, doi:10.1007/s00373-015-1651-1, MR 3514976, S2CID 41279514
^ Asplund, E.; Grünbaum, B. (1960), "On a coloring problem", Mathematica Scandinavica, 8: 181–188, doi:10.7146/math.scand.a-10607, MR 0144334
^ Chalermsook; Walczak (2020), "Coloring and Maximum Weight Independent Set of Rectangles", arXiv:2007.07880 [cs.CG]
^ Dvořák, Zdeněk; Král', Daniel (2012), "Classes of graphs with small rank decompositions are $\chi$ -bounded", European Journal of Combinatorics, 33 (4): 679–683, arXiv:1107.2161, doi:10.1016/j.ejc.2011.12.005, MR 3350076, S2CID 5530520
^ Kim, Seog-Jin; Kostochka, Alexandr; Nakprasit, Kittikorn (2004), "On the chromatic number of intersection graphs of convex sets in the plane", Electronic Journal of Combinatorics, 11 (1), R52, doi:10.37236/1805, MR 2097318
^ Davies, James (2022), "Improved bounds for colouring circle graphs", Proceedings of the American Mathematical Society, 150 (12): 5121–5135, arXiv:2107.03585, doi:10.1090/proc/16044
^ Rok, Alexandre; Walczak, Bartosz (2014), "Outerstring graphs are $\chi$ -bounded", Proceedings of the Thirtieth Annual Symposium on Computational Geometry (SoCG'14), New York: ACM, pp. 136–143, doi:10.1145/2582112.2582115, MR 3382292, S2CID 33362942
^ Rok, Alexandre; Walczak, Bartosz (2019), "Outerstring Graphs are χ-Bounded", SIAM Journal on Discrete Mathematics, 33 (4): 2181–2199, arXiv:1312.1559, doi:10.1137/17M1157374, S2CID 9474387
^ Rok, Alexandre; Walczak, Bartosz (2019), "Coloring Curves that Cross a Fixed Curve", Discrete & Computational Geometry, 61 (4): 830–851, arXiv:1512.06112, doi:10.1007/s00454-018-0031-z, S2CID 124706442
^ Chudnovsky, Maria; Seymour, Paul (2023), "Even-hole-free graphs still have bisimplicial vertices", Journal of Combinatorial Theory, Series B, 161: 331–381, arXiv:1909.10967, doi:10.1016/j.jctb.2023.02.009, MR 4568110
^ Kierstead, H. A.; Penrice, S. G. (1994), "Radius two trees specify $\chi$ -bounded classes", Journal of Graph Theory, 18 (2): 119–129, doi:10.1002/jgt.3190180203, MR 1258244
^ Briański, Marcin; Davies, James; Walczak, Bartosz (2023), "Separating polynomial $\chi$ -boundedness from $\chi$ -boundedness", Combinatorica, arXiv:2201.08814, doi:10.1007/s00493-023-00054-3, S2CID 246476859

External links

Chi-bounded, Open Problem Garden

[g87-1] Gyárfás, A. (1987), "Problems from the world surrounding perfect graphs" (PDF), Proceedings of the International Conference on Combinatorial Analysis and its Applications (Pokrzywna, 1985), Zastosowania Matematyki, 19 (3–4): 413–441 (1988), MR 0951359

[survey-2] Scott, Alex; Seymour, Paul (2020), "A survey of $\chi$ -boundedness", Journal of Graph Theory, 95 (3): 473–504, MR 4174126

[descartes-3] Descartes, Blanche (1947), "A three colour problem", Eureka, 21

[z-4] Zykov, A. A. (1949), "О некоторых свойствах линейных комплексов" [On some properties of linear complexes], Mat. Sbornik, New Series (in Russian), 24 (66): 163–188, MR 0035428. Translated into English in Amer. Math. Soc. Translation, 1952, MR0051516. As cited by Pawlik et al. (2014)

[m-5] Mycielski, Jan (1955), "Sur le coloriage des graphs", Colloq. Math. (in French), 3 (2): 161–162, doi:10.4064/cm-3-2-161-162, MR 0069494

[pkk-6] Pawlik, Arkadiusz; Kozik, Jakub; Krawczyk, Tomasz; Lasoń, Michał; Micek, Piotr; Trotter, William T.; Walczak, Bartosz (2014), "Triangle-free intersection graphs of line segments with large chromatic number", Journal of Combinatorial Theory, Series B, 105: 6–10, arXiv:1209.1595, doi:10.1016/j.jctb.2013.11.001, MR 3171778, S2CID 9705484

[cs-7] Chudnovsky, Maria; Seymour, Paul (2010), "Claw-free graphs VI. Colouring", Journal of Combinatorial Theory, Series B, 100 (6): 560–572, doi:10.1016/j.jctb.2010.04.005, MR 2718677

[km-8] Karthick, T.; Maffray, Frédéric (2016), "Vizing bound for the chromatic number on some graph classes", Graphs and Combinatorics, 32 (4): 1447–1460, doi:10.1007/s00373-015-1651-1, MR 3514976, S2CID 41279514

[ag60-9] Asplund, E.; Grünbaum, B. (1960), "On a coloring problem", Mathematica Scandinavica, 8: 181–188, doi:10.7146/math.scand.a-10607, MR 0144334

[max-10] Chalermsook; Walczak (2020), "Coloring and Maximum Weight Independent Set of Rectangles", arXiv:2007.07880 [cs.CG]

[dk12-11] Dvořák, Zdeněk; Král', Daniel (2012), "Classes of graphs with small rank decompositions are $\chi$ -bounded", European Journal of Combinatorics, 33 (4): 679–683, arXiv:1107.2161, doi:10.1016/j.ejc.2011.12.005, MR 3350076, S2CID 5530520

[kkn04-12] Kim, Seog-Jin; Kostochka, Alexandr; Nakprasit, Kittikorn (2004), "On the chromatic number of intersection graphs of convex sets in the plane", Electronic Journal of Combinatorics, 11 (1), R52, doi:10.37236/1805, MR 2097318

[circ-13] Davies, James (2022), "Improved bounds for colouring circle graphs", Proceedings of the American Mathematical Society, 150 (12): 5121–5135, arXiv:2107.03585, doi:10.1090/proc/16044

[rw14-14] Rok, Alexandre; Walczak, Bartosz (2014), "Outerstring graphs are $\chi$ -bounded", Proceedings of the Thirtieth Annual Symposium on Computational Geometry (SoCG'14), New York: ACM, pp. 136–143, doi:10.1145/2582112.2582115, MR 3382292, S2CID 33362942

[outer-15] Rok, Alexandre; Walczak, Bartosz (2019), "Outerstring Graphs are χ-Bounded", SIAM Journal on Discrete Mathematics, 33 (4): 2181–2199, arXiv:1312.1559, doi:10.1137/17M1157374, S2CID 9474387

[curv-16] Rok, Alexandre; Walczak, Bartosz (2019), "Coloring Curves that Cross a Fixed Curve", Discrete & Computational Geometry, 61 (4): 830–851, arXiv:1512.06112, doi:10.1007/s00454-018-0031-z, S2CID 124706442

[evenhole-17] Chudnovsky, Maria; Seymour, Paul (2023), "Even-hole-free graphs still have bisimplicial vertices", Journal of Combinatorial Theory, Series B, 161: 331–381, arXiv:1909.10967, doi:10.1016/j.jctb.2023.02.009, MR 4568110

[kp94-18] Kierstead, H. A.; Penrice, S. G. (1994), "Radius two trees specify $\chi$ -bounded classes", Journal of Graph Theory, 18 (2): 119–129, doi:10.1002/jgt.3190180203, MR 1258244

[bdw-19] Briański, Marcin; Davies, James; Walczak, Bartosz (2023), "Separating polynomial $\chi$ -boundedness from $\chi$ -boundedness", Combinatorica, arXiv:2201.08814, doi:10.1007/s00493-023-00054-3, S2CID 246476859

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]