Shifting paths to avoidable ones

Journal of Graph Theory. 2022. Vol. 100. No. 1. P. 69–83.

Gurvich V., Krnc M., Milanič M., Vyalyi M.

An extension of an induced path 𝑃P in a graph 𝐺G is an induced path 𝑃′P′ such that deleting the endpoints of 𝑃′P′ results in 𝑃P. An induced path in a graph is said to be avoidable if each of its extensions is contained in an induced cycle. In 2019, Beisegel, Chudovsky, Gurvich, Milanič, and Servatius conjectured that every graph that contains an induced 𝑘k-vertex path also contains an avoidable induced path of the same length, and proved the result for 𝑘=2k=2. The case 𝑘=1k=1 was known much earlier, due to a work of Ohtsuki, Cheung, and Fujisawa in 1976. The conjecture was proved for all 𝑘k in 2020 by Bonamy, Defrain, Hatzel, and Thiebaut. In the present paper, using a similar approach, we strengthen their result from a reconfiguration point of view. Namely, we show that in every graph, each induced path can be transformed to an avoidable one by a sequence of shifts, where two induced 𝑘k-vertex paths are shifts of each other if their union is an induced path with 𝑘+1k+1 vertices. We also obtain analogous results for not necessarily induced paths and for walks. In contrast, the statement cannot be extended to trails or to isometric paths.

Keywords: reconfiguration, walk, shifting, avoidable walk, closed walk, induced path

Publication based on the results of: Mathematical methods in studies of algorithmic complexity and formal languages (2021)