Gyárfás–Sumner conjecture
 |
Unsolved problem in mathematics: Does forbidding both a tree and a clique as induced subgraphs produce graphs of bounded chromatic number? (more unsolved problems in mathematics)
|
In graph theory, the Gyárfás–Sumner conjecture asks whether, for every tree [math]\displaystyle{ T }[/math] and complete graph [math]\displaystyle{ K }[/math], the graphs with neither [math]\displaystyle{ T }[/math] nor [math]\displaystyle{ K }[/math] as induced subgraphs can be properly colored using only a constant number of colors. Equivalently, it asks whether the [math]\displaystyle{ T }[/math]-free graphs are [math]\displaystyle{ \chi }[/math]-bounded.[1] It is named after András Gyárfás and David Sumner, who formulated it independently in 1975 and 1981 respectively.[2][3] It remains unproven.[4]
In this conjecture, it is not possible to replace [math]\displaystyle{ T }[/math] by a graph with cycles. As Paul Erdős and András Hajnal have shown, there exist graphs with arbitrarily large chromatic number and, at the same time, arbitrarily large girth.[5] Using these graphs, one can obtain graphs that avoid any fixed choice of a cyclic graph and clique (of more than two vertices) as induced subgraphs, and exceed any fixed bound on the chromatic number.[1]
The conjecture is known to be true for certain special choices of [math]\displaystyle{ T }[/math], including paths,[6] stars, and trees of radius two.[7] It is also known that, for any tree [math]\displaystyle{ T }[/math], the graphs that do not contain any subdivision of [math]\displaystyle{ T }[/math] are [math]\displaystyle{ \chi }[/math]-bounded.[1]
References
- ↑ 1.0 1.1 1.2 Scott, A. D. (1997), "Induced trees in graphs of large chromatic number", Journal of Graph Theory 24 (4): 297–311, doi:10.1002/(SICI)1097-0118(199704)24:4<297::AID-JGT2>3.3.CO;2-X
- ↑ "On Ramsey covering-numbers", Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vol. II, Colloq. Math. Soc. János Bolyai, 10, Amsterdam: North-Holland, 1975, pp. 801–816
- ↑ Sumner, D. P. (1981), "Subtrees of a graph and the chromatic number", The theory and applications of graphs (Kalamazoo, Mich., 1980), Wiley, New York, pp. 557–576
- ↑ "Extending the Gyárfás-Sumner conjecture", Journal of Combinatorial Theory, Series B 105: 11–16, 2014, doi:10.1016/j.jctb.2013.11.002
- ↑ "On chromatic number of graphs and set-systems", Acta Mathematica Academiae Scientiarum Hungaricae 17 (1–2): 61–99, 1966, doi:10.1007/BF02020444, https://users.renyi.hu/~p_erdos/1966-07.pdf
- ↑ "Problems from the world surrounding perfect graphs", Zastosowania Matematyki 19 (3–4): 413–441 (1988), 1987
- ↑ Kierstead, H. A.; Penrice, S. G. (1994), "Radius two trees specify χ-bounded classes", Journal of Graph Theory 18 (2): 119–129, doi:10.1002/jgt.3190180203
External links
- Graphs with a forbidden induced tree are chi-bounded, Open Problem Garden
 |  |
