Gyárfás-Sumner Conjecture

The Gyárfás--Sumner Conjecture

Definitions and mathematical statement

Shared notation.

Unless a section says otherwise, ${\mathbb{N}}=\{1,2,\ldots\}$, ${\mathbb{Z}}$ is the ring of integers, ${\mathbb{Q}},{\mathbb{R}},{\mathbb{C}}$ are the rational, real, and complex fields, $[N]=\{1,\ldots,\lfloor N\rfloor\}$, and $\log$ is the natural logarithm. For real functions of a parameter tending to infinity, $f\ll g$ and $f=O(g)$ mean $|f|\leq Cg$ eventually for some fixed $C$; $f\gg g$ reverses this comparison; $f=o(g)$ means $f/g\to0$; $f\sim g$ means $f/g\to1$; and $f\asymp g$ means both order bounds. A subscript on $O$ or $\ll$ specifies allowed constant dependence. The expression $n^{o(1)}$ in an upper bound means growth smaller than $n^\epsilon$ for each fixed $\epsilon>0$. Local definitions govern any exception, finite-field convention, or use of the same symbol for another object. An asymptotic claim is not automatically an effective algorithm.

For a finite graph $G$, let $\chi(G)$ be its chromatic number and $\omega(G)$ its clique number. For each fixed finite tree $T$, seek a function $f_T:{\mathbb{N}}\to{\mathbb{N}}$ such that every finite graph containing no induced copy of $T$ satisfies $\chi(G)\leq f_T(\omega(G))$. An induced copy preserves both adjacency and nonadjacency among its vertices. [S1] [S2]

Statement recorded in the supplied source.

Is every graph class defined by excluding one fixed tree as an induced subgraph

\ensuremath{χ}

-bounded? [S1]

Residual task reported by the archive.

The embedded review $2026-08-17$ records: Prove chi-boundedness for the class excluding each fixed tree as an induced subgraph. [S1]

Short English statement

Does excluding any one fixed tree as an induced subgraph bound a graph’s chromatic number in terms of its largest clique?

Research attempt

Status: UNRESOLVED. We prove the conjectured type of bound when the excluded tree is a star, and give elementary exact answers for paths on at most three vertices. We also derive a general minimum-degree embedding lemma and explain precisely why its non-induced conclusion cannot settle the target.

Literature and target hygiene.

Nguyen--Scott--Seymour [S3], consulted 1 October 2026, obtains a path-induced copy under bounded-clique and large-chromatic-number hypotheses. Its abstract explicitly distinguishes that property from a fully induced copy of the tree. We do the same: every pair of nonadjacent tree vertices must remain nonadjacent in an induced copy, including vertices lying on different branches. A copy preserving only root-to-leaf paths does not impose all those missing edges.

Finite Ramsey bound, with a direct derivation.

Let $R(a,b)$ denote the least order forcing an $a$-clique or an independent $b$-set. The vertex-neighborhood argument gives \[ R(a,b)\le R(a-1,b)+R(a,b-1),\qquad R(1,b)=R(a,1)=1. \] Indeed, among all other vertices either enough neighbours exist to apply the first term or enough nonneighbours to apply the second. Inducting with Pascal's identity yields \[ R(a,b)\le\binom{a+b-2}{a-1}. \] The bound is crude but finite and depends only on its two parameters. This suffices for the star case without any asymptotic Ramsey theorem.

A complete bound for excluded stars.

Let $T=K_{1,t}$ with $t\ge2$, and let $\omega(G)\le w$. In the neighborhood of any vertex there is no clique of size $w$, since adjoining the vertex would create a $(w+1)$-clique. There is no independent $t$-set either, since that set together with the vertex would induce $K_{1,t}$. Hence \[ \deg(v)<R(w,t),\qquad \chi(G)\le\Delta(G)+1\le R(w,t) \le\binom{w+t-2}{w-1}. \] The ordinary greedy colouring theorem used here follows by colouring vertices in any order: at most $\Delta$ colours can be forbidden at a vertex. For $w=1$, the graph is edgeless, and the same conclusion is immediate. This proves the required function $f_T$ for every fixed star.

The proof depends on the induced nature of the forbidden star. The leaves must be pairwise nonadjacent, which is why the neighborhood independent-set alternative is the correct Ramsey obstruction. Finding $t$ arbitrary neighbours would give only a non-induced star and would not use the hypothesis correctly.

The shortest paths.

If the excluded tree is a single edge, the graph is edgeless. If it is the three-vertex path, every connected component of a graph with no induced such path is complete. To prove this, assume two nonadjacent vertices lie in one component and take a shortest path between them. Its first three vertices have consecutive edges and no shortcut edge; they induce a three-vertex path, a contradiction. A disjoint union of cliques has $\chi=\omega$, because the same palette can be reused on different components. Thus $f_T(w)=w$ works in this case.

If the excluded tree has one vertex, the only avoiding graph is empty; it may be treated separately with chromatic number zero. These edge cases do not force a convention that accidentally excludes nonempty edgeless graphs from the other arguments.

The tempting minimum-degree argument and its limitation.

Every graph of minimum degree at least $t-1$ contains every tree on $t$ vertices as an ordinary subgraph. Root the tree and embed its vertices in an order in which every vertex after the root has its parent already embedded. When adding a vertex, at most $t-2$ already used vertices other than its parent can occupy neighbours of that parent. Degree at least $t-1$ therefore leaves an unused neighbour. This constructs an injective edge-preserving map.

A graph of chromatic number at least $t$ contains a subgraph of minimum degree at least $t-1$: repeatedly deleting smaller-degree vertices would otherwise yield a greedy $(t-1)$-colouring in reverse order. Combining the two facts forces an ordinary copy of every $t$-vertex tree.

The construction does not forbid the chosen new vertex from also being adjacent to other previously embedded vertices. In a complete graph it creates every tree as a subgraph, yet no induced noncomplete tree. Bounding the clique number removes that particular counterexample but does not supply the missing nonadjacency constraints. One needs a reservoir of candidates avoiding all unwanted branches, rather than merely a large neighborhood of the parent.

Verification and remaining gap.

All statements here are proved directly, with no finite enumeration or novel literature claim. The star bound depends only on $w$ and the fixed number of leaves, never on $|G|$, as the target requires. The ordinary embedding lemma was deliberately not promoted to an induced embedding lemma.

For a general fixed tree, the exact remaining step is controlling unwanted edges between different branches while retaining enough chromatic number to continue an embedding. Neither the star neighborhood bound nor the minimum-degree lemma establishes that control. The full Gyárfás--Sumner target remains unresolved by this attempt.

Sources

• S1 ULAM.AI, UnsolvedMath, supplied problems.json, record 1397 (GRAPH-010), statement and background. The embedded literature-review date is 2026-08-17; that is the archive’s review date, not a fresh certification. Dataset landing page: https://huggingface.co/datasets/ulamai/UnsolvedMath.

• S2 A. Scott and P. Seymour, A survey of chi-boundedness, J. Graph Theory 95 $2020$. https://doi.org/10.1002/jgt.22511. Bibliographic information from the supplied record.

• S3 P. Chudnovsky et al., A note on the Gyárfás-Sumner conjecture, arXiv:2302.08922 $2023$. https://arxiv.org/abs/2302.08922. Bibliographic information from the supplied record.