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.
References
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
No solutions have been posted yet.