A vertex  in a graph  is avoidable if every induced path on three vertices with middle vertex  is contained in an induced cycle. Dirac’s classical result from 1961 on the existence of simplicial vertices in chordal graphs is equivalent to the statement that every chordal graph has an avoidable vertex. Beisegel, Chudovsky, Gurvich, Milani\v{c}, and Servatius (2019) generalized the notion of avoidable vertices to \emph{avoidable paths}, and conjectured that every graph that contains an induced -vertex path also contains an avoidable induced -vertex path; they proved the result for . The case  was known much earlier, due to a work of Ohtsuki, Cheung, and Fujisawa in 1976. The conjecture was proved for all  in 2020 by Bonamy, Defrain, Hatzel, and Thiebaut. This result generalizes the mentioned results regarding avoidable vertices, as well as a result by Chv\’atal, Rusu, and Sritharan (2002) suggested by West on the existence of simplicial -vertex paths in graphs excluding induced cycles of length at least  .

In this talk we discuss an adaptation of the approach by Bonamy et al.~from a reconfiguration point of view. We say that two induced -vertex paths are \emph{shifts} of each other if their union is an induced path with  vertices and show that in every graph, every induced path can be shifted to an avoidable one. We also present an analogous result about paths that are not necessarily induced, where an efficient reconfiguration sequence relies on the properties of depth-first search trees.

 Join Zoom Meeting Here!