The induced rainbow path conjecture for triangle-free graphs
The induced rainbow path conjecture for triangle-free graphs
Let be a finite simple triangle-free graph, let be its chromatic number, and let be a proper vertex coloring, where . A path in is rainbow if all its vertices have distinct colors under , and induced if no two nonconsecutive vertices of the path are adjacent in . Induced rainbow path conjecture. Every colored triangle-free graph contains an induced rainbow path on 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
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.