Avoidable Paths in Graphs

 

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\’atal et al.~2002, which assumed cycle restrictions. We provide a constructive and elementary proof, relying on a single trick regarding the induction hypothesis.

This is joint work with  Marthe Bonamy, Oscar Defrain and Jocelyn Thiebaut.