We prove a recent conjecture of Beisegel et al. that for every positive integer $k$, every graph containing an induced $P_k$ also contains an avoidable $P_k$. Avoidability generalises the notion of simpliciality best known in the context of chordal graphs. The conjecture was only established for $k \in \{1,2\}$ (Ohtsuki et al. 1976, and Beisegel et al. 2019, respectively). Our result also implies a result of Chvátal et al. 2002, which assumed cycle restrictions. We provide a constructive and elementary proof, relying on a single trick regarding the induction hypothesis. In the line of previous works, we discuss conditions for multiple avoidable paths to exist.
@article{10_37236_9030,
author = {Marthe Bonamy and Oscar Defrain and Meike Hatzel and Jocelyn Thiebaut},
title = {Avoidable paths in graphs},
journal = {The electronic journal of combinatorics},
year = {2020},
volume = {27},
number = {4},
doi = {10.37236/9030},
zbl = {1454.05058},
url = {http://geodesic.mathdoc.fr/articles/10.37236/9030/}
}
TY - JOUR
AU - Marthe Bonamy
AU - Oscar Defrain
AU - Meike Hatzel
AU - Jocelyn Thiebaut
TI - Avoidable paths in graphs
JO - The electronic journal of combinatorics
PY - 2020
VL - 27
IS - 4
UR - http://geodesic.mathdoc.fr/articles/10.37236/9030/
DO - 10.37236/9030
ID - 10_37236_9030
ER -
%0 Journal Article
%A Marthe Bonamy
%A Oscar Defrain
%A Meike Hatzel
%A Jocelyn Thiebaut
%T Avoidable paths in graphs
%J The electronic journal of combinatorics
%D 2020
%V 27
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/9030/
%R 10.37236/9030
%F 10_37236_9030
Marthe Bonamy; Oscar Defrain; Meike Hatzel; Jocelyn Thiebaut. Avoidable paths in graphs. The electronic journal of combinatorics, Tome 27 (2020) no. 4. doi: 10.37236/9030
