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?

In graph theory, the Gyárfás–Sumner conjecture asks whether, for every tree $T$ and complete graph $K$ , the graphs with neither $T$ nor $K$ as induced subgraphs can be properly colored using only a constant number of colors. Equivalently, it asks whether the $T$ -free graphs are $\chi$ -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 $T$ 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 $T$ , including paths,^[6] stars, and trees of radius two.^[7] It is also known that, for any tree $T$ , the graphs that do not contain any subdivision of $T$ are $\chi$ -bounded.^[1]

References

^ ^a ^b ^c Scott, A. D. (1997), "Induced trees in graphs of large chromatic number", Journal of Graph Theory, 24 (4): 297–311, CiteSeerX 10.1.1.176.1458, doi:10.1002/(SICI)1097-0118(199704)24:4<297::AID-JGT2>3.3.CO;2-X, MR 1437291
^ Gyárfás, A. (1975), "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, vol. 10, Amsterdam: North-Holland, pp. 801–816, MR 0382051
^ 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, MR 0634555
^ Chudnovsky, Maria; Seymour, Paul (2014), "Extending the Gyárfás-Sumner conjecture", Journal of Combinatorial Theory, Series B, 105: 11–16, doi:10.1016/j.jctb.2013.11.002, MR 3171779
^ Erdős, P.; Hajnal, A. (1966), "On chromatic number of graphs and set-systems" (PDF), Acta Mathematica Academiae Scientiarum Hungaricae, 17 (1–2): 61–99, doi:10.1007/BF02020444, MR 0193025
^ Gyárfás, A. (1987), "Problems from the world surrounding perfect graphs", Proceedings of the International Conference on Combinatorial Analysis and its Applications (Pokrzywna, 1985), Zastosowania Matematyki, 19 (3–4): 413–441 (1988), MR 0951359
^ 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, MR 1258244