Polynomial detection of holes mod 3

Open Question: Detecting Holes of Length Divisible by Three · arXiv:2009.05691

arXiv Question medium confidence— first stated 2020-09-12

Authors: Linda Cook, Paul Seymour

Status open high confidence

No polynomial-time algorithm for detecting holes (induced cycles) whose length is divisible by three has been found in the literature, and no hardness result has been established either. Cook's subsequent PhD thesis (arXiv:2312.11876, 2023) extends the even-hole detection line of work but does not address holes divisible by three. The question posed in arXiv:2009.05691 remains fully open as of May 2026.

Reviewer notes. Linda Cook's PhD thesis (arXiv:2312.11876) is the most relevant follow-up work by a co-author, but it focuses on even holes of length at least l (for fixed l >= 4), not on holes of length divisible by three. A structural result on graphs with no hole divisible by three (bounded chromatic number via Parity Changing Paths) appears in unrelated literature, but recognition/detection complexity remains untouched. No follow-up found after exhaustive search.

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

Question. Can holes whose length is a multiple of three be detected in polynomial time?

Context

Having focused on even and odd holes, the authors remark: "what about holes of length a multiple of three, can we detect them in polynomial time? Triangle-free graphs with no holes of length a multiple of three have some very interesting properties [9], but we currently have no idea how to recognize such graphs." This suggests the problem of recognising graphs with no hole of length $\equiv 0 \pmod{3}$ as a natural next direction.

Notes. Stated informally in the introduction as a rhetorical open question; no labelled environment.

Source paper

Detecting a long even hole
Linda Cook, Paul Seymour · 2020-09-12
https://arxiv.org/abs/2009.05691 PDF source