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]

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 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 any subdivision of ${\displaystyle T}$ are ${\displaystyle \chi }$-bounded.^[1]