The linear-logarithmic induced-path conjecture for triangle-free graphs
Let be a triangle-free graph with chromatic number . An induced path is a path whose vertices induce exactly the edges of the path.
Linear-logarithmic induced-path conjecture. There is some constant such that every triangle-free graph of chromatic number contains an induced path of length at least .
This is a quantitative strengthening of the known fact that triangle-free graphs of chromatic number contain induced paths of length at least . 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
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.