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
