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

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.

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

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.