Stable set meeting all longest directed paths.

Medium ★★ Graph Theory

Authors: Laborde, Jean-Marie, Payan, Charles, Xuong N.H.— posted by fhavet on 2013-03-01

Status open medium confidence

The conjecture that every digraph has a stable set meeting all longest directed paths remains open. The only verified partial result—Havet's 2004 proof for digraphs with stability number at most 2—predates the OPG posting, as does Fox and Sudakov's 2009 proof of the complementary Hahn-Jackson conjecture. No post-2013 papers extending the conjecture to stability number $\geq 3$ or to the general case were found in multiple targeted searches.

Reviewer notes. The DMGT article at dmgt.uz.zgora.pl/publish/article.php?doi=1650 appeared repeatedly in searches but was inaccessible due to SSL certificate errors. The AJC 2014 paper (ajc.maths.uq.edu.au/pdf/59/ajc_v59_p311.pdf) was a binary PDF that could not be read; it is possible this contains a partial result on this conjecture. All clearly post-2013 arXiv papers found (arXiv:2402.16776 on Thomassé's conjecture; arXiv:2302.04986 on P5-free graphs) are unrelated to the LPX conjecture. Confidence is medium rather than high due to these two inaccessible sources.

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

Conjecture. Every digraph has a stable set meeting all longest directed paths

Discussion

If the stability number is 1, that is if the digraph is a tournament, it follows Redei's Theorem stating that every tournament has a directed hamiltonian path. The conjecture has been proved by Havet [H] for digraphs having stability number 2. The conjecture would give an easy inductive proof of Gallai-Roy Theorem: every digraph with chromatic number $ k $ contains a directed path on $ k $ vertices. Hahn and Jackson [HJ] conjectured that in contrast there is no directed path meeting every maximum stable set. In fact, they conjectured the following: For each positive integer $ k $ , there is a digraph $ D $ with stability number $ k $ such that deleting the vertices of any $ k-1 $ directed paths in $ D $ leaves a digraph with stability number $ k $ . This was proved by Fox and Sudakov [FS] by a probabilistic argument.

Bibliography

[FS] J. Fox and B. Sudakov, Paths and stability number in digraphs, Electronic Journal of Combiantorics, 16 (2009), no.1, N23.
[HJ] G. Hahn and B. Jackson, A note concerning paths and independence number in digraphs, Discrete Math. 82 (1990), 327–329.
[H] F. Havet. Stable set meeting every longest path. Discrete Mathematics, 289 (2004), no. 1-3, 169-173.
★ [LPX] J.M. Laborde, C. Payan, and N.H. Xuong, Independent sets and longest directed paths in digraphs. In Graphs and other Combinatorial Topics (Prague, 1982)}, Teubner-Texte Math., Vol. 59 (1983), 173-177, Teubner, Leipzig.