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

DOI10.1006/jctb.2001.2055zbMath1023.05115OpenAlexW1969592750MaRDI QIDQ1850573

Steé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

partitionpathsstable setindependence numberstability numberforestarborescence

Mathematics Subject Classification ID

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

Related Items (6)

The complexity of finding arc-disjoint branching flows ⋮ Structural properties of minimal strong digraphs versus trees ⋮ 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 ⋮ Structural and spectral properties of minimal strong digraphs ⋮ Balanced branchings in digraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sur les arborescences dans un graphe oriente
• Every finite strongly connected digraph of stability 2 has a Hamiltonian path
• A short proof of the Chen-Manalastas theorem
• Path Partitions in Directed Graphs

This page was built for publication: Covering a strong digraph by \(\alpha-1\) disjoint paths: A proof of Las Vergnas' conjecture