Heavy path extension for long odd holes
Informal Conjecture (heavy path extension) · arXiv:1904.12273
Status open medium confidence
The heavy path conjecture from Conjecture (informal) in arXiv:1904.12273 — that when one vertex of a C-major set M is nonadjacent to all others, a single path of C of bounded length catches every vertex of M — was explicitly left unresolved by the authors, who replaced it with a more complicated argument. A targeted web search across 2020–2026 found no follow-up paper proving or disproving this specific statement. Given the conjecture is ~6 years old and the search returned nothing, absence of published progress is plausible but not certain for such a technical algorithmic lemma.
Reviewer notes. No follow-up paper specifically addressing the heavy path extension was found after 5 web calls. The statement is informal (not labelled as a formal conjecture in the paper) and concerns a structural lemma internal to an algorithmic proof; progress may exist in unpublished notes or in successor papers not indexed by the queries used. Related follow-up work by the same group (arXiv:2004.11874 on shortest odd hole, arXiv:2009.05691 on long even holes) was identified but not verified to address this specific conjecture.
Context
The authors attempted to extend the 'heavy edge' lemma from the odd hole algorithm of [6] to the long odd hole setting: a 'heavy path' of bounded length containing a neighbour of every vertex in $M$ would suffice for constructing the cleaning list. The authors believe the extension is plausible but were unable to prove it, and had to use a more complicated replacement argument instead.
Notes. Stated as 'this extension might be true, but we were unable to prove it.' No formal labelled environment. PDF source — math notation may be partially garbled.
Source paper
Detecting a long odd hole
Maria Chudnovsky, Alex Scott, Paul Seymour · 2020-09-06
https://arxiv.org/abs/1904.12273
PDF source