The induced rainbow path conjecture for triangle-free graphs

Let GG be a finite simple triangle-free graph, let χ(G)\chi(G) be its chromatic number, and let ϕ:V(G)[k]\phi:V(G)\to[k] be a proper vertex coloring, where k=χ(G)k=\chi(G). A path in GG is rainbow if all its vertices have distinct colors under ϕ\phi, and induced if no two nonconsecutive vertices of the path are adjacent in GG. Induced rainbow path conjecture. Every colored triangle-free graph (G,ϕ)(G,\phi) contains an induced rainbow path on χ(G)\chi(G) vertices. This would simultaneously strengthen the known existence of induced paths and rainbow paths of order equal to the chromatic number in colored triangle-free graphs. The conjecture remains open in general, although several partial results are known.

Sources & referencesView supporting material

Primary source

N. R. Aravind, Shiwali Gupta and Rogers Mathew, “Towards a conjecture on long induced rainbow paths in triangle-free graphs”, arXiv:2601.00602 (2026).

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.