Berge's Conjecture on Directed Path Partitions - A Survey <s> For bipartite digraphs. <s> 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. <s> BIB001 </s> Berge's Conjecture on Directed Path Partitions - A Survey <s> For bipartite digraphs. <s> 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. <s> BIB002 </s> Berge's Conjecture on Directed Path Partitions - A Survey <s> For bipartite digraphs. <s> 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 . <s> BIB003 </s> Berge's Conjecture on Directed Path Partitions - A Survey <s> For bipartite digraphs. <s> 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. <s> BIB004 </s> Berge's Conjecture on Directed Path Partitions - A Survey <s> For bipartite digraphs. <s> 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. <s> BIB005
If G is acyclic then Conjecture 2.6 was shown to be true in BIB001 and independently in  . Moreover, Conjecture 2.8 was proved for acyclic digraphs in  , BIB003 and BIB002 . In fact, a stronger result holds for acyclic digraphs: Theorem 2.9 (  , BIB003 and BIB002 ) Let G be an acyclic digraph, and let k be a positive integer. Then there exists a k-colouring C k which is orthogonal to every k-optimal path partition P of G. Obviously, Theorem 2.9 implies Berge's Conjecture (Conjecture 2.8) in the case that G is acyclic. Theorem 2.9 is not true for all digraphs, as was shown by a counter-example in BIB002 . Aharoni and Hartman  proved that Berge's Conjecture holds also in the case that the k-optimal path partition has only long paths, i.e. paths of cardinality at least k. Another possible extension of Theorem 2.3 is by considering a partition of V into disjoint paths and cycles, called path-cycle partition. The k-norm of a path cycle partition with m paths and an arbitrary number of cycles is defined as: Note that by this definition cycles do not count in the k-norm. Similarly, a path-cycle partition P c and a k-colouring C k are orthogonal if each path P i ∈ P c meets min{|P |, k} different colour classes of C k , and each cycle C i ∈ P c can meet any arbitrary number of vertices in C k . With this new definition of orthogonality, Hartman  proved, using the proof technique described in section 2.2.1, the following: Theorem 2.10 (I.B.A. Hartman  ) Let G be any digraph, and let k be a positive integer. Then there exists a k-colouring C k which is orthogonal to every k-optimal path-cycle partition P c of G. Another partial result on Berge's Conjecture is by Sridharan BIB004 BIB005 , who proved it in the case that the underlying undirected graph has no two cycles intersecting in a unique vertex. In the following section we shall discuss various proof techniques for proving Berge's Conjecture (Conjecture 2.8) for acyclic digraphs.