A short proof of the Chen-Manalastas theorem

DOI10.1016/0012-365X(94)00173-1zbMath0839.05078OpenAlexW2030550589MaRDI QIDQ1903737

J. A. Bondy

Publication date: 18 June 1996

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0012-365x(94)00173-1

zbMATH Keywords

digraphstability numbercircuitpath partitionChen-Manalastas theorem

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Directed graphs (digraphs), tournaments (05C20)

Related Items (7)

Advances in Aharoni-Hartman-Hoffman's conjecture for split digraphs ⋮ Every strong digraph has a spanning strong subgraph with at most \(n+2\alpha-2\) arcs ⋮ Berge's conjecture on directed path partitions -- a survey ⋮ Paths partition with prescribed beginnings in digraphs: A Chvátal-Erdős condition approach ⋮ Spannning a strong digraph by \(\alpha\) circuits: a proof of Gallai's conjecture ⋮ Stable set meeting every longest path ⋮ Covering a strong digraph by \(\alpha-1\) disjoint paths: A proof of Las Vergnas' conjecture

Cites Work

• Variations on the Gallai-Milgram theorem
• Every finite strongly connected digraph of stability 2 has a Hamiltonian path
• Chvátal-Erdős conditions for paths and cycles in graphs and digraphs. A survey
• Path Partitions in Directed Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A short proof of the Chen-Manalastas theorem