On Greene-Kleitman's theorem for general digraphs

DOI10.1016/0012-365X(93)90561-7zbMath0786.05037MaRDI QIDQ687099

Ron Aharoni, Irith Ben-Arroyo Hartman

Publication date: 5 May 1994

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

zbMATH Keywords

partitiondirected graphpathcoloringacyclic graphsGreene-Kleitman's theorem

Mathematics Subject Classification ID

Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20)

Related Items

Berge's conjecture on directed path partitions -- a survey, Proof of Berge's strong path partition conjecture for \(k=2\), A unified approach to known and unknown cases of Berge's conjecture, Berge's conjecture and Aharoni-Hartman-Hoffman's conjecture for locally in-semicomplete digraphs, Path Partitions, Cycle Covers and Integer Decomposition, Acyclic digraphs with Gallai-Milgram-Linial property for clique-covers

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Path partitions and packs of acyclic digraphs
• Some sequences associated with combinatorial structures
• On k-optimum dipath partitions and partial k-colourings of acyclic digraphs
• A short proof of the existence of k-saturated partitions of partially ordered sets
• On chain and antichain families of a partially ordered set
• Extending the Greene-Kleitman theorem to directed graphs
• k-optimal partitions of a directed graph
• Some partitions associated with a partially ordered set
• Extending Greene's theorem to directed graphs
• A decomposition theorem for partially ordered sets
• Acyclic Digraphs, Young Tableaux and Nilpotent Matrices
• Nombre chromatique et plus longs chemins d'un graphe
• The structure of Sperner k-families