Aravind's induced rainbow path conjecture
Aravind's induced rainbow path conjecture
A graph is properly colored if adjacent vertices receive distinct colors, and a vertex-colored graph is rainbow if no two vertices have the same color. A graph is triangle-free if it contains no triangle. Aravind's conjecture. Every properly colored triangle-free graph contains an induced rainbow path on vertices. This is a rainbow strengthening of the known theorem that every triangle-free graph contains an induced path on vertices; the supplied text does not state whether the conjecture has been resolved.
Sources & referencesView supporting material
Primary source
Manu Basavaraju, L. Sunil Chandran, Mathew C. Francis and Karthik Murali, “Variants of the Gyàrfàs-Sumner Conjecture: Oriented Trees and Rainbow Paths”, arXiv:2111.13115 (2024).
Additional references
2 papers in this index state this conjecture (2019–2021). The statement above is taken from the most recent of them; the others are arXiv:1912.13328.
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.