1National Research University Higher School of Economics and RUTCOR, Rutgers University, New Jersey, USA 2University of Primorska 3National Research University Higher School of Economics; Moscow Institute of Physics and Technology; Federal Research Center “Computer Science and Control” of the Russian Academy of Science
The electronic journal of combinatorics, Tome 32 (2025) no. 2
The concept of avoidable paths in graphs was introduced by Beisegel, Chudnovsky, Gurvich, Milanič, 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. We provide both positive and negative results, some of which are related to a recent work by Chudnovsky, Norin, Seymour, and Turcotte in 2024. We also discuss several open questions.
Vladimir Gurvich
1
;
Matjaž Krnc
2
;
Martin Milanič
2
;
Mikhail Vyalyi
3
1
National Research University Higher School of Economics and RUTCOR, Rutgers University, New Jersey, USA
2
University of Primorska
3
National Research University Higher School of Economics; Moscow Institute of Physics and Technology; Federal Research Center “Computer Science and Control” of the Russian Academy of Science
@article{10_37236_13023,
author = {Vladimir Gurvich and Matja\v{z} Krnc and Martin Milani\v{c} and Mikhail Vyalyi},
title = {Avoidability beyond paths},
journal = {The electronic journal of combinatorics},
year = {2025},
volume = {32},
number = {2},
doi = {10.37236/13023},
zbl = {1565.05095},
url = {http://geodesic.mathdoc.fr/articles/10.37236/13023/}
}
TY - JOUR
AU - Vladimir Gurvich
AU - Matjaž Krnc
AU - Martin Milanič
AU - Mikhail Vyalyi
TI - Avoidability beyond paths
JO - The electronic journal of combinatorics
PY - 2025
VL - 32
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/13023/
DO - 10.37236/13023
ID - 10_37236_13023
ER -
%0 Journal Article
%A Vladimir Gurvich
%A Matjaž Krnc
%A Martin Milanič
%A Mikhail Vyalyi
%T Avoidability beyond paths
%J The electronic journal of combinatorics
%D 2025
%V 32
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/13023/
%R 10.37236/13023
%F 10_37236_13023
Vladimir Gurvich; Matjaž Krnc; Martin Milanič; Mikhail Vyalyi. Avoidability beyond paths. The electronic journal of combinatorics, Tome 32 (2025) no. 2. doi: 10.37236/13023
