Avoidable paths in graphs (Q2215468): Difference between revisions

(The terminology follows the convention that an induced \(\dots\) is an induced subgraph which is also a \(\dots\).) For a graph \(G=(V,E)\), a vertex \(v\in V\) is avoidable if every induced path on three vertices with middle vertex \(v\) is contained in an induced cycle of \(G\). Let \(P\) be an induced path; an extension of \(P\) is an induced path obtained by extending \(P\) by one edge at both ends; the extension is failing if it is not contained in an induced cycle of \(G\); \(P\) is avoidable if it has no failing extension. Theorem 9 proves, for every \(\ell\ge 0\), that every graph that contains an induced path of length \(\ell\) also contains an avoidable induced path of length \(\ell\), which resolves Conjecture 1.1 of [\textit{J. Beisegel} et al., Lect. Notes Comput. Sci. 11646, 126--139 (2019; Zbl 07152205)]; case \(\ell=0\) was established in [\textit{T. Ohtsuki} et al., J. Math. Anal. Appl. 54, 622--633 (1976; Zbl 0371.65006); in: 2nd supplement to the Proceedings of the 6th Hawaii international conference on system sciences. 1973, University of Hawaii, Honolulu, HI. North Hollywood, CA: Western Periodicals Company. 49--52 (1973; Zbl 0357.65024)] etc., and case \(\ell=1\) in Theorem 6 of the cited paper of Beisegel et al. [loc. cit.]. The general conjecture was also motivated by results of \textit{V. Chvátal} et al. [Discrete Math. 256, No. 1--2, 445--448 (2002; Zbl 1011.05050)].