Rainbow induced-path conjecture for KrK_r-free graphs

About 7 years old · traced to

Let r≥3r\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 r≥3r\geq 3, every properly coloured KrK_r-free graph of chromatic number χ\chi contains a rainbow induced path of length χ1/(r−2)\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.

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

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.