The avoidable induced path conjecture
The avoidable induced path conjecture
Let be a graph, and let denote an induced path on vertices. An induced path is avoidable if every extension of is contained in an induced cycle, where an extension is an induced path obtained by adding one edge to at each end. Avoidable induced path conjecture. For every , every graph that contains an induced also contains an avoidable induced . This conjecture would simultaneously generalize the avoidable-vertex theorem and the result that graphs with no induced cycles of lengths at least contain a simplicial induced ; 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
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.