In this conjecture, it is not possible to replace 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 , including paths,[6]stars, and trees of radius two.[7]
It is also known that, for any tree , the graphs that do not contain any subdivision of are -bounded.[1]
^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, MR0382051
^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, MR0634555
^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), MR0951359