# Berge's conjecture on path partitions

Let *D* be a digraph without loops and *k* a positive integer. For a partition [math]\Pi[/math] of *V(D)* into directed paths (a **path partition**) let

[math]|\Pi|_k=\sum_{P \in \Pi}\min\{|P|,k\},[/math]

where [math]|P|[/math] is the number of nodes of the path (which can be 1). A **partial k-colouring** is the union of *k* stable sets. Is it true that for every path partition [math]\Pi[/math] minimizing [math]|\Pi|_k[/math], there exists a partial *k*-colouring which meets each path [math]P\in \Pi[/math] in [math]\min\{|P|,k\}[/math] stable sets?

## Remarks

A weaker conjecture was first proposed by Linial^{[1]}: *The minimum of [math]|\Pi|_k[/math] over all path partitions is at most the maximum size of a partial k-colouring.*

This weaker conjecture holds for *k=1* by the Gallai-Milgram theorem^{[2]}, which states that the minimum cardinality of a path partition is at most the independence number of the digraph. In fact, the standard proof of the Gallai-Milgram theorem shows that also Berge's conjecture holds for *k=1*.

For transitive acyclic digraphs the conjecture follows from the Greene-Kleitman theorem. Linial^{[1]} showed that his weaker conjecture holds if *D* is acyclic; later it was shown by several authors independently that the following is also true:

**Theorem.** *If D is acyclic, then there exists a partial k-colouring for which the property in Berge's conjecture holds for every path partition [math]\Pi[/math] minimizing [math]|\Pi|_k[/math].*

This is however not true for every digraph.

## Recent results

Let [math]\lambda[/math] be the number of vertices in the longest path of of the digraph. The conjecture holds if [math]k \geq \lambda[/math] by the Gallai-Roy theorem. Linial's conjecture follows from a theorem of Sebő^{[3]} if [math]k=\lambda-1[/math].
Berger and Hartman recently proved that Berge's conjecture holds for *k=2*^{[4]} and for [math]k=\lambda-1[/math] ^{[5]}. Sebő also observed that if the digraph is strongly connected, then a min-max theorem on Cyclic stable sets implies that the conjecture holds if [math]k \geq \lambda-\sqrt{\lambda}[/math]. Using a min-max theorem on path-cycle partitions and a careful choice of maximal acyclic subdigaph, Herskovics ^{[6]} showed that Berge's conjecture holds for [math]k \geq \lambda-3[/math].

## References

- ↑
^{1.0}^{1.1}N. Linial,*Extending the Greene-Kleitman theorem to directed graphs*, J. Combin. Theory Ser. A 30 (1981), 331-334. DOI link - ↑ T. Gallai, A. N. Milgram,
*Verallgemeinerung eines graphentheoretischen Satzes von Rédei*, Acta Sci. Math. 21 (1960), 181-186, journal link - ↑ A. Sebő,
*Path Partitions, Cycle Covers and Integer Decomposition*, Lecture Notes in Computer Science 5420 (2009), 183-199. DOI link, author link - ↑ E. Berger, I. B-A. Hartman,
*Proof of Berge's strong path partition conjecture for k=2*, European Journal of Combinatorics 29 (2008), 179-192. DOI link - ↑ E. Berger, I. B-A. Hartman,
*A unified approach to known and unknown cases of Berge's conjecture*, DOI link, author link - ↑ D. Herskovics,
*Proof of Berge's path partition conjecture for [math]k \geq \lambda-3[/math]*, EGRES Technical Report no. 2013-08