Rainbow induced-path conjecture for -free graphs
Rainbow induced-path conjecture for -free graphs
Let , and let be a properly coloured -free graph with chromatic number , where denotes the complete graph on vertices. A rainbow induced path is an induced path whose vertices all receive distinct colours.
Rainbow induced-path conjecture. For each , every properly coloured -free graph of chromatic number contains a rainbow induced path of length .
This generalises the triangle-free case and is related to quantitative bounds for independent sets in -free graphs. The source notes partial progress and that the assertion without the rainbow condition is known; the rainbow statement remains open.
Sources & referencesView supporting material
Primary source
N. R. Aravind, Stijn Cambie, Wouter Cames van Batenburg, Rémi de Joannis de Verclos, Ross J. Kang and Viresh Patel, “Structure and colour in triangle-free graphs”, arXiv:1912.13328 (2020).
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.