Gyárfás–Sumner conjecture

If a finite network has no large group of mutually joined dots, can banning one fixed branching pattern put a limit on how many colors it needs, regardless of its size? Joined dots must receive different colors. Five dots joined in a ring need three colors even though no three are all mutually joined. A tree is a connected pattern with no cycle. Banning it means that no selected dots show exactly that tree, including its missing connections. The conjecture says that fixing the tree and the maximum size of a mutually joined group always gives a finite color limit.[1] [2]

Can forbidding one fixed branching pattern, while limiting groups of mutually joined vertices, put a finite cap on needed colors regardless of graph size? The pattern is a tree: a connected graph with no cycle. A proper coloring assigns different colors to adjacent vertices, and the chromatic number $\chi(G)$ is the minimum needed. The clique number $\omega(G)$ is the largest pairwise adjacent vertex set. The five-cycle has $\omega=2$ and $\chi=3$; three consecutive vertices induce a path, because their endpoints are nonadjacent. An induced subgraph keeps every edge between the chosen vertices, not merely the ones used to trace the tree. For each fixed tree $T$ and positive integer $k$, the conjecture seeks a finite $f(T,k)$ with $\chi(G)\le f(T,k)$ whenever $\omega(G)\le k$ and no induced copy of $T$ occurs.[1] [2]

The statement is known for some trees, but remains open for an arbitrary fixed tree in arbitrary finite graphs. A 2026 theorem covers graphs represented by intersecting boxes in a fixed number of dimensions. That extra geometric restriction is not part of the general conjecture.[1]

The general conjecture asks for a finite bound, without prescribing how fast it grows. Davies and Yuditsky obtain a polynomial bound for graphs that are intersection graphs of axis-aligned boxes in a fixed dimension: vertices represent boxes, and edges represent intersecting pairs. The dimension is an additional fixed parameter. Their theorem does not bound every graph avoiding the tree.[1]

A mutually joined group clearly needs one color per dot, yet other arrangements can require extra colors without enlarging that group. The conjecture asks whether every sufficiently large coloring demand, after bounding such groups, must reveal any chosen tree pattern. This would identify a structural reason for global coloring complexity in terms of small, exactly preserved patterns.[1] [2]

Large chromatic number and small clique number can coexist, so pairwise dense groups are only one source of coloring complexity. The conjecture would make every fixed tree unavoidable once that complexity is sufficiently large under a fixed clique cap. Trees are the natural candidates: the cited survey explains why forbidding a pattern containing a cycle can still leave graphs with arbitrarily large chromatic number and small cliques. This places the problem within the broader search for which induced structures control coloring.[1] [2]