Berge's Conjecture on Directed Path Partitions - A Survey <s> Strongly Connected Graphs <s> 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. <s> BIB001 </s> Berge's Conjecture on Directed Path Partitions - A Survey <s> Strongly Connected Graphs <s> 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. <s> BIB002 </s> Berge's Conjecture on Directed Path Partitions - A Survey <s> Strongly Connected Graphs <s> 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). <s> BIB003 </s> Berge's Conjecture on Directed Path Partitions - A Survey <s> Strongly Connected Graphs <s> 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. <s> BIB004
A digraph G is strongly connected, or for brevity, strong, if for any ordered pair of vertices (x, y), there exists a path from x to y in G. The following well known theorem by Camion  strengthens the Gallai-Milgram Theorem (Theorem 1.1) in the case that α(G) = 1 and G is strong. Theorem 4.1 (Camion[24] ) A strongly connected tournament contains a Hamilton cycle. In view of Camion's Theorem it is natural to attempt to strengthen the Gallai-Milgram Theorem for all α, in the case of strong digraphs. Chen and Manalastas  have done so for α = 2. Theorem 4.2 (Chen and Manalastas  ) Every strongly connected digraph G with α(G) = 2 is spanned by two consistent cycles 3 . An alternative proof of Theorem 4.2 can be found in BIB003 . An immediate result of Theorem 4.2 is that every strong digraph with α = 2 is spanned by a Hamilton path. Thomassé proved the following theorem which was originally conjectured by Las-Vergnas  . Another attempt to strengthen the Gallai-Milgram Theorem is Gallai's conjecture  from 1963, only recently proved by Bessy and Thomassé BIB004 : Theorem 4.5 (Bessy and Thomassé BIB004 ) Every strongly connected digraph G is spanned by the union of α(G) cycles. As a corollary, we get for α = 1 Camion's Theorem. The case α = 2 is a corollary of the ChenManalastas Theorem (Theorem 4.2). If G is an undirected graph with connectivity κ(G) and independence number α(G) ≤ k, then by the Chvátal-Erdős Theorem  G contains a Hamilton cycle. As a corollary, it follows that if This can be seen by constructing a new graph G * from G by adding α(G) − κ new vertices to G and joining them to each vertex in V (G). The resultant graph G * has connectivity κ = α(G * ), and hence contains a Hamilton cycle, implying that V (G) can be partitioned into α(G) − κ paths. This is clearly a strengthening of the Gallai-Milgram Theorem for undirected graphs. Can we have such a strengthening for directed graphs? The graph in Figure 5 has k = α = 2 and contains no Hamilton cycle, thus showing that the Chvátal-Erdős Theorem cannot necessarily be extended to directed graphs. Also the example given by Bondy BIB003 , the digraph obtained from the composition of K 1,3 with K 2 , is 2-connected, has α = 3, but contains no Hamilton path. Other counterexamples for k = 2 and k = 3 also exist. (see  and BIB002 ). The following is a more reasonable extension of the Chvátal-Erdős Theorem to directed graphs. Conjecture 4.7 (Bessy and Thomassé [15] ) Let G be a k-connected directed graph with α ≥ k. Then V (G) can be partitioned into at most α disjoint cycles. For other possible extensions of the Chvátal-Erdős theorem to directed graphs see  , BIB001 , and [15] .  . . . Now that the Gallai-Milgram Theorem has been strengthened for strong digraphs, it is reasonable to ask whether the Gallai-Roy Theorem can be similarly strengthened. If G is a tournament (i.e. χ(G) = n) then G contains a Hamilton path. This special case of the Gallai-Roy Theorem is known as Rédei's Theorem  . If G is a strong tournament, then, as we have already seen, Camion's Theorem (Theorem 4.1) implies the existence of a Hamilton cycle. The following theorem by Bondy  , originally conjectured by Las-Vergnas, strengthens the Gallai-Roy Theorem for strong digraphs. Theorem 4.8 (Bondy  ) Every strongly connected digraph contains a directed cycle of length at least χ. Corollary 4.9 Let G be strongly connected digraph with n ≥ χ(G) + 1. Then λ(G) ≥ χ(G) + 1. 5 α-and χ-diperfect graphs.