The avoidable induced path conjecture

Let GG be a graph, and let PkP_k denote an induced path on kk vertices. An induced path PP is avoidable if every extension of PP is contained in an induced cycle, where an extension is an induced path obtained by adding one edge to PP at each end. Avoidable induced path conjecture. For every k1k\ge 1, every graph that contains an induced PkP_k also contains an avoidable induced PkP_k. This conjecture would simultaneously generalize the avoidable-vertex theorem and the result that graphs with no induced cycles of lengths at least k+3k+3 contain a simplicial induced PkP_k; its status is not resolved in the supplied source.

Sources & referencesView supporting material

Primary source

Jesse Beisegel, Maria Chudnovsky, Vladimir Gurvich, Martin Milanič and Mary Servatius, “Avoidable Vertices and Edges in Graphs”, arXiv:1907.12078 (2019).

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.