The colourful induced-subgraph conjecture for forests

Let GG be a finite simple graph. For a vertex vV(G)v\in V(G), write NG[v]=NG(v){v}N_G[v]=N_G(v)\cup\{v\}, and call GG ε\varepsilon-colourful if

χ(GNG[v])<εχ(G)\chi(G\setminus N_G[v])<\varepsilon\chi(G)

for every vV(G)v\in V(G). For an induced subgraph FF of GG, use the same definition with FF in place of GG. Colourful induced-subgraph conjecture. For every ε>0\varepsilon>0 and every forest TT, there exists δ>0\delta>0 such that every TT-free graph GG has an ε\varepsilon-colourful induced subgraph FF with χ(F)δχ(G)\chi(F)\ge\delta\chi(G). This asserts the existence of a locally dense induced subgraph carrying a linear proportion of the chromatic number. It is known for T=P4T=P_4 and for stars, but the source says it is undecided for T=P5T=P_5 and even for the two-edge matching.

Sources & referencesView supporting material

Primary source

Tung H. Nguyen, “On polynomially high-chromatic pure pairs”, arXiv:2504.21127 (2026).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.