Avoidable non-path family existence

Question 4.1 · arXiv:1908.03788

arXiv Question high confidence— first stated 2019-08-10

Authors: Marthe Bonamy, Oscar Defrain, Meike Hatzel, Jocelyn Thiebaut

Status partial medium confidence

Question 4.1 is directly addressed by Gurvich, Krnc, Milanič, and Vyalyi in 'Avoidability beyond paths' (arXiv:2208.12803, published in Electronic Journal of Combinatorics 2025). That paper introduces a framework of two-rooted graphs to generalise avoidability beyond paths, and provides both positive and negative results about which connected non-path structures admit an avoidability property. The question is not fully resolved: no family H satisfying the exact condition of Question 4.1 is identified, but the framework clarifies structural obstructions and establishes partial answers for restricted graph classes such as C5-free graphs.

Cited literature (1)

partial Avoidability beyond paths (2022)

Vladimir Gurvich, Matjaž Krnc, Martin Milanič, Mikhail Vyalyi · The Electronic Journal of Combinatorics · arXiv:2208.12803

Directly addresses Question 4.1 by introducing a two-rooted graph framework for avoidability beyond paths; provides both positive results (for special graph classes) and negative results, but does not produce a family H satisfying the full question.

Reviewer notes. The follow-up paper arXiv:2208.12803 is the primary response to Question 4.1; it was published in the Electronic Journal of Combinatorics (v32i2p27). The paper addresses the question with a generalised framework but does not settle it with a definitive yes or no for the full statement. Confidence is medium because the full text was not read — only the abstract and partial HTML were accessible.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Question. Does there exist a family $\mathcal{H}$ of connected graphs, not containing any path, such that any graph is either $\mathcal{H}$-free or contains an avoidable element of $\mathcal{H}$?

Context

Having established avoidable paths of every length, the authors ask whether avoidability extends to other graph structures. They note that even allowing a family rather than a single pattern, no candidate beyond paths seems to survive tests on chordal graphs or simple ad hoc constructions, and that the notion of avoidability for non-path structures is deliberately left open to interpretation.

Notes. PDF source — mathematical content is clear; the family $\mathcal{H}$ notation is inferred from context.

Source paper

Avoidable paths in graphs
Marthe Bonamy, Oscar Defrain, Meike Hatzel, Jocelyn Thiebaut · 2019-08-10
https://arxiv.org/abs/1908.03788 PDF source