# Berge's conjecture on path partitions

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

$|\Pi|_k=\sum_{P \in \Pi}\min\{|P|,k\},$

where $|P|$ 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 $\Pi$ minimizing $|\Pi|_k$, there exists a partial k-colouring which meets each path $P\in \Pi$ in $\min\{|P|,k\}$ stable sets?

## Remarks

A weaker conjecture was first proposed by Linial[1]: The minimum of $|\Pi|_k$ 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 $\Pi$ minimizing $|\Pi|_k$.

This is however not true for every digraph.

## Recent results

Let $\lambda$ be the number of vertices in the longest path of of the digraph. The conjecture holds if $k \geq \lambda$ by the Gallai-Roy theorem. Linial's conjecture follows from a theorem of Sebő[3] if $k=\lambda-1$. Berger and Hartman recently proved that Berge's conjecture holds for k=2[4] and for $k=\lambda-1$ [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 $k \geq \lambda-\sqrt{\lambda}$. 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 $k \geq \lambda-3$.

## References

1. N. Linial, Extending the Greene-Kleitman theorem to directed graphs, J. Combin. Theory Ser. A 30 (1981), 331-334. DOI link
2. T. Gallai, A. N. Milgram, Verallgemeinerung eines graphentheoretischen Satzes von Rédei, Acta Sci. Math. 21 (1960), 181-186, journal link
3. A. Sebő, Path Partitions, Cycle Covers and Integer Decomposition, Lecture Notes in Computer Science 5420 (2009), 183-199. DOI link, author link
4. 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
5. E. Berger, I. B-A. Hartman, A unified approach to known and unknown cases of Berge's conjecture, DOI link, author link
6. D. Herskovics, Proof of Berge's path partition conjecture for $k \geq \lambda-3$, EGRES Technical Report no. 2013-08