The concept of avoidable paths in graphs was introduced by Beisegel, Chudnovsky, Gurvich, Milani\v{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.
翻译:Beisegel、Chudnovsky、Gurvich、Milani\v{c}和Serviatius于2019年提出了图表中可避免路径的概念,作为可避免的脊椎和简易路径的共同概括。 2020年,Bonamy、Debrain、Hatzel和Thiebaut证明,每个含有诱导的顺序路径的图表都含有同一顺序的可避免引导路径。他们还询问,是否可以将这一结果概括到其他可避免的结构中,将可避免性的概念留待解释。 在本文中,我们讨论这一问题:我们具体说明了配有两顶顶脊的任意图的可避免性概念,并提供了正和负结果。