The linear-logarithmic induced-path conjecture for triangle-free graphs
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.
Sources & referencesView supporting material
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
Sign in to submit a solution.
No solutions have been posted yet.