Disjoint avoidable Pₖ pairs existence

Question 1.12 · arXiv:1908.03788

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

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

Status disproved high confidence

Question 1.12 is resolved negatively within the same paper: the authors provide an explicit counterexample for every k >= 3 (a cycle on 2k-1 vertices with one additional vertex adjacent to two consecutive cycle vertices), showing that two disjoint P_k need not contain two disjoint avoidable P_k. The cases k in {1,2} have positive answers by results of Beisegel et al. A web search found no follow-up papers further studying this specific question.

Reviewer notes. The counterexample is given within the source paper itself (not in a follow-up), so there are no since_posted entries. The related paper 'Avoidability beyond paths' (arXiv:2208.12803, Gurvich, Krnc, Milanič, 2022) extends avoidability to two-rooted graphs but does not directly address Question 1.12 about disjoint paths.

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

Question. For every positive integer $k$, does every graph $G$ either not contain two disjoint $P_k$, or contain two disjoint avoidable $P_k$?

Context

The analogous statement for non-adjacent avoidable $P_k$ is established as Corollary 1.11. The authors note the answer is positive for $k \in \{1,2\}$ by results of Beisegel et al., but then provide an explicit counterexample for every $k \geq 3$ (a cycle on $2k-1$ vertices with one extra vertex adjacent to two consecutive cycle vertices), resolving the question negatively within the same paper.

Notes. The question is posed and then fully answered (negatively for $k \geq 3$) within the same paper; it is not open.

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