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 GG contains an induced rainbow path on χ(G)\chi(G) vertices. This is a rainbow strengthening of the known theorem that every triangle-free graph contains an induced path on χ(G)\chi(G) 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

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.