Shifting paths to avoidable ones
share
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. Beisegel, Chudovsky, Gurvich, Milanič, and Servatius (WADS 2019) 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 k = 2 (the case k = 1 was known before). The same year Bonamy, Defrain, Hatzel, and Thiebaut proved the conjecture for all k. Here we strengthen their result and show that every induced path can be shifted to an avoidable one. We also prove analogous results for the non-induced case and for the case of walks, and show that the statement cannot be extended to trails or to isometric paths.
READ FULL TEXT