Gyárfás–Sumner conjecture

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