Berge's conjecture on path partitions

From Egres Open
Jump to: navigation, search

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?


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].


  1. 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
  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 [math]k \geq \lambda-3[/math], EGRES Technical Report no. 2013-08