← All problems

Seymour’s openly disjoint cycles problem

For every positive integer rr and every finite rr-regular digraph DD, let c(D)c(D) be the maximum cardinality of a collection of directed cycles in DD that all contain a common vertex and are pairwise openly disjoint, meaning that any two cycles have no common vertex other than that common vertex. Seymour's problem asks whether c(D)=rc(D)=r for every such DD.

References

Source: arXiv

Progress summary

Refreshed
Open · progress reported

A new paper improves the bounds and finds counterexamples in degrees six and seven, while the main growth question remains open.

Seymour posed the equality question in 2005: whether every rr-regular digraph has c(D)=rc(D)=r. The general equality fails in all degrees r≥8r\geq 8, but degrees 44 and 55 remain unresolved.

Known results

  • r=1r=1: trivial.
  • r=2r=2: positive result of Thomassen.
  • r=3r=3: positive result of Mader (2009).
  • Steiner established ⌈3r/22⌉≤cr≤7⌈r/8⌉\left\lceil 3r/22\right\rceil\leq c_r\leq 7\left\lceil r/8\right\rceil, implying cr→∞c_r\to\infty.

October 2026 improved bounds and counterexamples

Bin Chen, Wenshen Wu, and Meishuang Chen claim 66- and 77-regular counterexamples with c(D)=5c(D)=5 and c(D)=6c(D)=6, respectively. They also claim

⌈r/6⌉≤cr≤5⌈r/6⌉,\left\lceil r/6\right\rceil\leq c_r\leq 5\left\lceil r/6\right\rceil,

so the limiting ratio lies between 1/61/6 and 5/65/6; determining it remains open.

Current status (as of November 2026): The equality question is settled negatively for r≥6r\geq 6 and r≥8r\geq 8 by the cited results, while r∈{4,5}r\in\{4,5\} and the limiting ratio lim⁡r→∞cr/r\lim_{r\to\infty}c_r/r remain open; the new claims are unverified.

Sources

Solutions 0

No solutions have been posted yet.