Berge's Conjecture on Directed Path Partitions - A Survey
---
paper_title: A Decomposition Theorem for Partially Ordered Sets

paper_content:

Otherwise a and b are non-comparable. A subset S of P is independent if every two distinct elements of S are non-comparable. S is dependent if it contains two distinct elements which are comparable. A subset C of P is a chain if every two of its elements are comparable.
---
paper_title: A short proof of the Chen-Manalastas theorem

paper_content:

Abstract Gallai and Milgram (1960) proved that a digraph with stability number α is spanned by α disjoint directed paths. Chen and Manalastas Jr (1983) proved that a strong digraph with stability number at most two is spanned by at most two consistent directed circuits. We slightly simplify the proof of the Gallai-Milgram theorem, while at the same time refining its statement, and use this sharpened version to obtain a relatively short proof of the Chen-Manalastas theorem. We also give a counterexample to a generalization of the Gallai-Milgram theorem conjectured by Hartman (1988).
---
paper_title: On chain and antichain families of a partially ordered set

paper_content:

Abstract A common generalization of the theorems of Greene and Greene and Kleitman is presented. This yields some insight into the relation of optimal chain and antichain families of a partially ordered set. The fundamental device is the minimal cost flow algorithm of Ford and Fulkerson.
---
paper_title: The Structure of Sperner k-families

paper_content:

Abstract If P is a partially ordered set, a k-family of P is a subset which contains no chains of length k + 1. This paper examines the structure of the set of k-families of P. An extension of Dilworth's theorem is obtained by relating the maximum size of a k-family to certain partitions of P into chains. A natural lattice ordering on k-families is defined and analyzed, and a number of strong intersection properties are obtained. Finally, the k-families of P are used to define a class of submodular set functions on P, which can be used to generalize a number of results in transversal theory.
---
paper_title: Path partitions and packs of acyclic digraphs.

paper_content:

Let G be an acyclic directed graph with \V(G)\>k. We prove that there exists a colouring { Cx, C2,..., Cm } such that for every collection {Pl9 P2,... ,Pk} of k vertex disjoint paths with |UjLi Pj\ a maximum, each colour class C, meets min{|CJ, k} of these paths. An analogous theorem, partially interchanging the roles of paths and colour classes, has been shown by Cameron [4] and Saks [17] and we indicate a third proof.
---
paper_title: Extending the Greene-Kleitman theorem to directed graphs

paper_content:

The celebrated Dilworth theorem (Ann. of Math. 51 (1950), 161–166) on the decomposition of finite posets was extended by Greene and Kleitman (J. Combin. Theory Ser. A 20 (1976), 41–68). Using the Gallai-Milgram theorem (Acta Sci. Math. 21 (1960), 181–186) we prove a theorem on acyclic digraphs which contains the Greene-Kleitman theorem. The method of proof is derived from M. Saks' elegant proof (Adv. in Math. 33 (1979), 207–211) of the Greene-Kleitman theorem.
---
paper_title: On the strong path partition conjecture of Berge

paper_content:

Abstract It is proved that for every k -optimal path partition of a directed graph in which no two cycles interesect at a vertex, there exists a partial k -coloring which colors strongly each path of the partition.
---
paper_title: On the Berge's strong path partition conjecture

paper_content:

Abstract It is proved that for every k -optimal path partition of a diagraph in which each component contains at most one cycle, there exists a partial k -coloring which colors strongly every path of the partition.
---
paper_title: Path partitions and packs of acyclic digraphs.

paper_content:

Let G be an acyclic directed graph with \V(G)\>k. We prove that there exists a colouring { Cx, C2,..., Cm } such that for every collection {Pl9 P2,... ,Pk} of k vertex disjoint paths with |UjLi Pj\ a maximum, each colour class C, meets min{|CJ, k} of these paths. An analogous theorem, partially interchanging the roles of paths and colour classes, has been shown by Cameron [4] and Saks [17] and we indicate a third proof.
---
paper_title: Extending the Greene-Kleitman theorem to directed graphs

paper_content:

The celebrated Dilworth theorem (Ann. of Math. 51 (1950), 161–166) on the decomposition of finite posets was extended by Greene and Kleitman (J. Combin. Theory Ser. A 20 (1976), 41–68). Using the Gallai-Milgram theorem (Acta Sci. Math. 21 (1960), 181–186) we prove a theorem on acyclic digraphs which contains the Greene-Kleitman theorem. The method of proof is derived from M. Saks' elegant proof (Adv. in Math. 33 (1979), 207–211) of the Greene-Kleitman theorem.
---
paper_title: On k-optimum dipath partitions and partial k-colourings of acyclic diagraphs

paper_content:

For an acyclic digraph G and positive integer k , we give a min-max equality for: minimum { k ℘ + V ( G ) − ∪ ℘ } : ℘ is a node-disjoint set of dipaths in G } We prove that there exist k independent sets { S j : j = 1, 2,..., k } such that for every optimum ℘, every P ∈℘; intersects each S j , and every dipath P in G −∪℘; intersects | P | different sets S j .
---
paper_title: Path partitions and packs of acyclic digraphs.

paper_content:

Let G be an acyclic directed graph with \V(G)\>k. We prove that there exists a colouring { Cx, C2,..., Cm } such that for every collection {Pl9 P2,... ,Pk} of k vertex disjoint paths with |UjLi Pj\ a maximum, each colour class C, meets min{|CJ, k} of these paths. An analogous theorem, partially interchanging the roles of paths and colour classes, has been shown by Cameron [4] and Saks [17] and we indicate a third proof.
---
paper_title: On k-optimum dipath partitions and partial k-colourings of acyclic diagraphs

paper_content:

For an acyclic digraph G and positive integer k , we give a min-max equality for: minimum { k ℘ + V ( G ) − ∪ ℘ } : ℘ is a node-disjoint set of dipaths in G } We prove that there exist k independent sets { S j : j = 1, 2,..., k } such that for every optimum ℘, every P ∈℘; intersects each S j , and every dipath P in G −∪℘; intersects | P | different sets S j .
---
paper_title: On chain and antichain families of a partially ordered set

paper_content:

Abstract A common generalization of the theorems of Greene and Greene and Kleitman is presented. This yields some insight into the relation of optimal chain and antichain families of a partially ordered set. The fundamental device is the minimal cost flow algorithm of Ford and Fulkerson.
---
paper_title: The Structure of Sperner k-families

paper_content:

Abstract If P is a partially ordered set, a k-family of P is a subset which contains no chains of length k + 1. This paper examines the structure of the set of k-families of P. An extension of Dilworth's theorem is obtained by relating the maximum size of a k-family to certain partitions of P into chains. A natural lattice ordering on k-families is defined and analyzed, and a number of strong intersection properties are obtained. Finally, the k-families of P are used to define a class of submodular set functions on P, which can be used to generalize a number of results in transversal theory.
---
paper_title: ON MATROID INTERSECTIONS

paper_content:

This paper exploits and extends results of Edmonds, Cunningham, Cruse and McDiarmid on matroid intersections. Letr 1 andr 2 be rank functions of two matroids defined on the same setE. For everyS ⊂E, letr 12(S) be the largest cardinality of a subset ofS independent in both matroids, 0≦k≦r 12(E)−1. It is shown that, ifc is nonnegative and integral, there is ay: 2 E →Z + which maximizes\(\sum\limits_S {(k - r_{12} (E - S))y(S)} \) and\(\sum\limits_S {(k + 1 - r_{12} (E - S))y(S)} \), subject toy≧0, ∀j∈E,\(\sum\limits_{S \mathrel\backepsilon j} {y(S) \leqq c_j } \).
---
paper_title: On partitions of a partially ordered set

paper_content:

Abstract Using linear programming we prove a generalization of Greene and Kleitman's generalization of Dilworth's theorem on the decomposition of a partially ordered set into chains.
---
paper_title: On chain and antichain families of a partially ordered set

paper_content:

Abstract A common generalization of the theorems of Greene and Greene and Kleitman is presented. This yields some insight into the relation of optimal chain and antichain families of a partially ordered set. The fundamental device is the minimal cost flow algorithm of Ford and Fulkerson.
---
paper_title: Extending Greene's theorem to directed graphs

paper_content:

Abstract The purpose of this note is to prove a theorem on acyclic digraphs, conjectured by Linial (J. Combin. Theory Ser. A, 30 (1981), 331–334), which includes Greene's theorem (J. Combin. Theory Ser. A, 20 (1976), 69–79) on decompositions of a partially ordered set into antichains.
---
paper_title: Path partitions and packs of acyclic digraphs.

paper_content:

Let G be an acyclic directed graph with \V(G)\>k. We prove that there exists a colouring { Cx, C2,..., Cm } such that for every collection {Pl9 P2,... ,Pk} of k vertex disjoint paths with |UjLi Pj\ a maximum, each colour class C, meets min{|CJ, k} of these paths. An analogous theorem, partially interchanging the roles of paths and colour classes, has been shown by Cameron [4] and Saks [17] and we indicate a third proof.
---
paper_title: Extending the Greene-Kleitman theorem to directed graphs

paper_content:

The celebrated Dilworth theorem (Ann. of Math. 51 (1950), 161–166) on the decomposition of finite posets was extended by Greene and Kleitman (J. Combin. Theory Ser. A 20 (1976), 41–68). Using the Gallai-Milgram theorem (Acta Sci. Math. 21 (1960), 181–186) we prove a theorem on acyclic digraphs which contains the Greene-Kleitman theorem. The method of proof is derived from M. Saks' elegant proof (Adv. in Math. 33 (1979), 207–211) of the Greene-Kleitman theorem.
---
paper_title: Spanning a strong digraph by α circuits: A proof of Gallai’s conjecture

paper_content:

In 1963, Tibor Gallai [9] asked whether every strongly connected directed graph D is spanned by α directed circuits, where α is the stability of D. We give a proof of this conjecture.
---
paper_title: A short proof of the Chen-Manalastas theorem

paper_content:

Abstract Gallai and Milgram (1960) proved that a digraph with stability number α is spanned by α disjoint directed paths. Chen and Manalastas Jr (1983) proved that a strong digraph with stability number at most two is spanned by at most two consistent directed circuits. We slightly simplify the proof of the Gallai-Milgram theorem, while at the same time refining its statement, and use this sharpened version to obtain a relatively short proof of the Chen-Manalastas theorem. We also give a counterexample to a generalization of the Gallai-Milgram theorem conjectured by Hartman (1988).
---
paper_title: Variations on the Gallai-Milgram theorem

paper_content:

Abstract We strengthen the Gallai-Milgram theorem for digraphs with independence number two, and propose various problems and conjectures strengthening the Gallai-Milgram theorem and the Gallai-Roy theorem for strong digraphs.
---
paper_title: A Chvátal-Erdös condition for (1, 1)-factors in digraphs

paper_content:

Abstract We show that if the independence number of a k -connected digraph D is at most k , then D has a spanning subgraph which consists of a union of vertex-disjoint directed circuits. As a corollary we determine the minimum number of edges required in a k -connected oriented graph to ensure the existence of such a subgraph.
---
paper_title: The strong perfect graph theorem

paper_content:

A graph G is perfect if for every induced subgraph H, the chromatic number of H equals the size of the largest complete subgraph of H, and G is Berge if no induced subgraph of G is an odd cycle of length at least 5 or the complement of one. The"strong perfect graph conjecture"(Berge, 1961) asserts that a graph is perfect if and only if it is Berge. A stronger conjecture was made recently by Conforti, Cornuejols and Vuskovic -- that every Berge graph either falls into one of a few basic classes, or it has a kind of separation that cannot occur in a minimal imperfect graph. In this paper we prove both these conjectures.
---

Title: Berge's Conjecture on Directed Path Partitions - A Survey

Section 1: Introduction and definitions
Description 1: Provide background information, key terminologies, and foundational results related to path partitions in directed graphs.

Section 2: Extending the Greene-Kleitman theorem
Description 2: Discuss the generalization of Dilworth's Theorem by Greene and Kleitman, introducing k-colourings and optimal k-colourings in digraphs.

Section 3: Proof techniques for extending the Greene-Kleitman theorem
Description 3: Describe various proof techniques such as Linear Programming, Cartesian Products, and Network Flows and Bipartite Graphs, used to extend the Greene-Kleitman theorem to acyclic digraphs.

Section 4: Extending the theorems of Gallai-Roy and Greene
Description 4: Explain the dual concepts involving colourings and k-path systems, stating related theorems and conjectures that extend the work of Gallai, Roy, and Greene.

Section 5: Strongly Connected Graphs
Description 5: Analyze theorems and strengthenings related to strongly connected digraphs, including Camion's Theorem and the work of Chen, Manalastas, Bessy, and Thomassé.

Section 6: α-and χ-diperfect graphs
Description 6: Investigate the concepts of α-diperfect and χ-diperfect digraphs, discussing conjectures, known results, and extensions provided by Berge and others.