Rainbow induced-path conjecture for KrK_r-free graphs

Let r3r\geq 3, and let GG be a properly coloured KrK_r-free graph with chromatic number χ\chi, where KrK_r denotes the complete graph on rr vertices. A rainbow induced path is an induced path whose vertices all receive distinct colours.

Rainbow induced-path conjecture. For each r3r\geq 3, every properly coloured KrK_r-free graph of chromatic number χ\chi contains a rainbow induced path of length χ1/(r2)\chi^{1/(r-2)}.

This generalises the triangle-free case and is related to quantitative bounds for independent sets in KrK_r-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

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.