The colourful induced-subgraph conjecture for forests
The colourful induced-subgraph conjecture for forests
Let be a finite simple graph. For a vertex , write , and call -colourful if
for every . For an induced subgraph of , use the same definition with in place of . Colourful induced-subgraph conjecture. For every and every forest , there exists such that every -free graph has an -colourful induced subgraph with . This asserts the existence of a locally dense induced subgraph carrying a linear proportion of the chromatic number. It is known for and for stars, but the source says it is undecided for 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.