Paths and stability number in digraphs

MaRDI QIDQ2380212zbMATH OpenFDO

Authors Jacob Fox, Benny Sudakov

Publication date 26 March 2010

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0905.2644, https://eudml.org/doc/230739, http://www.emis.de/journals/EJC/Volume_16/Abstracts/v16i1n23.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

stabilitydirected pthsdographGallai Milgram theoremvertex set partition

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38) Generalized Ramsey theory (05C55)

Abstract: The Gallai-Milgram theorem says that the vertex set of any digraph with stability number k can be partitioned into k directed paths. In 1990, Hahn and Jackson conjectured that this theorem is best possible in the following strong sense. 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. In this note, we prove this conjecture.

Recommendations

• Lexicographic products and a conjecture of Hahn and Jackson
• scientific article; zbMATH DE number 3891403
• Covering a strong digraph by \(\alpha-1\) disjoint paths: A proof of Las Vergnas' conjecture
• On the strong path partition conjecture of Berge
• Paths partition with prescribed beginnings in digraphs: A Chvátal-Erdős condition approach

Cited in

(14)

• Variations on the Gallai-Milgram theorem
• Paths partition with prescribed beginnings in digraphs: A Chvátal-Erdős condition approach
• On the strong path partition conjecture of Berge
• scientific article; zbMATH DE number 4198025 (Why is no real title available?)
• A short proof of the Chen-Manalastas theorem
• Digraphs products
• Stable set meeting every longest path
• Lexicographic products and a conjecture of Hahn and Jackson
• On greene's theorem for digraphs
• Covering a strong digraph by \(\alpha-1\) disjoint paths: A proof of Las Vergnas' conjecture
• A note concerning paths and independence number in digraphs
• scientific article; zbMATH DE number 1868869 (Why is no real title available?)
• scientific article; zbMATH DE number 3891403 (Why is no real title available?)
• Spannning a strong digraph by \(\alpha\) circuits: a proof of Gallai's conjecture

This page was built for publication: Paths and stability number in digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2380212)