The linear-logarithmic induced-path conjecture for triangle-free graphs

About 7 years old · traced to

Let GG be a triangle-free graph with chromatic number χ\chi. An induced path is a path whose vertices induce exactly the edges of the path.

Linear-logarithmic induced-path conjecture. There is some constant c>0c>0 such that every triangle-free graph of chromatic number χ\chi contains an induced path of length at least cχlog⁡χc\chi\log\chi.

This is a quantitative strengthening of the known fact that triangle-free graphs of chromatic number χ\chi contain induced paths of length at least χ\chi. The supplied status evidence concerns a different Gyárfás conjecture, so this conjecture is retained as 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.