Avoidability beyond paths
From MaRDI portal
Publication:6408958
arXiv2208.12803MaRDI QIDQ6408958FDOQ6408958
Authors: Vladimir Gurvich, Matjaž Krnc, Martin Milanič, Mikhail Vyalyi 
Publication date: 26 August 2022
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 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)
