Avoidability beyond paths

MaRDI QIDQ6408958zbMATH OpenFDO

Authors Vladimir Gurvich, Matjaž Krnc, Martin Milanič, Mikhail Vyalyi

Publication date 26 August 2022

Mathematics Subject Classification ID

Paths and cycles (05C38) Structural characterization of families of graphs (05C75)

Abstract: The concept of avoidable paths in graphs was introduced by Beisegel, Chudnovsky, Gurvich, Milaniv{c}, and Servatius in 2019 as a common generalization of avoidable vertices and simplicial paths. In 2020, Bonamy, Defrain, Hatzel, and Thiebaut proved that every graph containing an induced path of order $k$ also contains an avoidable induced path of the same order. They also asked whether one could generalize this result to other avoidable structures, leaving the notion of avoidability up to interpretation. In this paper we address this question: we specify the concept of avoidability for arbitrary graphs equipped with two terminal vertices and provide both positive and negative results.

This page was built for publication: Avoidability beyond paths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6408958)