Covering a strong digraph by -1 disjoint paths: A proof of Las Vergnas' conjecture

DOI10.1006/JCTB.2001.2055MaRDI QIDQ1850573zbMATH OpenOpenAlexFDO

Authors Stéphan Thomassé

Publication date 10 December 2002

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jctb.2001.2055

zbMATH Keywords

partitionpathsforestindependence numberarborescencestable setstability number

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 3891403
• Spannning a strong digraph by \(\alpha\) circuits: a proof of Gallai's conjecture
• Paths and stability number in digraphs
• Variations on the Gallai-Milgram theorem
• Every strong digraph has a spanning strong subgraph with at most \(n+2\alpha-2\) arcs

Cites work

• scientific article; zbMATH DE number 3150485 (Why is no real title available?)
• scientific article; zbMATH DE number 3165195 (Why is no real title available?)
• scientific article; zbMATH DE number 863469 (Why is no real title available?)
• A short proof of the Chen-Manalastas theorem
• Every finite strongly connected digraph of stability 2 has a Hamiltonian path
• Path Partitions in Directed Graphs
• Sur les arborescences dans un graphe oriente

Cited in

(14)

• Variations on the Gallai-Milgram theorem
• A short proof of the Chen-Manalastas theorem
• BE-diperfect digraphs with stability number two
• A minimum semi-degree sufficient condition for one-to-many disjoint path covers in semicomplete digraphs
• Every strong digraph has a spanning strong subgraph with at most \(n+2\alpha-2\) arcs
• The complexity of finding arc-disjoint branching flows
• Berge's conjecture on directed path partitions -- a survey
• Structural properties of minimal strong digraphs versus trees
• Lexicographic products and a conjecture of Hahn and Jackson
• Paths and stability number in digraphs
• Balanced branchings in digraphs
• Structural and spectral properties of minimal strong digraphs
• 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: Covering a strong digraph by \(\alpha-1\) disjoint paths: A proof of Las Vergnas' conjecture

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