Berge's conjecture on path partitions

Definitions and mathematical statement

Let $D=(V,A)$ be a finite loopless digraph and $k\ge1$. A directed path has distinct vertices and follows the directions of its successive arcs; a single vertex is permitted. A path partition $\Pi$ consists of vertex-disjoint directed paths covering $V$. Define its $k$-cost by \[ c_k(\Pi)=\sum_{P\in\Pi}\min\{|V(P)|,k\}. \] A partial $k$-colouring is a collection $I_1,\ldots,I_k$ of pairwise disjoint stable vertex sets, some possibly empty. Stability means that no arc in either direction joins two vertices in the same set; vertices outside their union remain uncoloured.

Berge's conjecture states that every path partition minimizing $c_k$ admits such a partial colouring with \[ |V(P)\cap(I_1\cup\cdots\cup I_k)|=\min\{|V(P)|,k\}, \qquad |V(P)\cap I_j|\le1 \] for every $P\in\Pi$ and every colour $j$. Thus each path meets the required number of distinct colour classes. The quantifier concerns every minimum-cost partition, not the existence of one particularly convenient optimum. The paths are not required to be induced, longest individually, or of equal length. A bound on the total number of coloured vertices alone would miss the stipulated compatibility with each separate path of the given partition.

Short English statement

Can every minimum-cost directed path partition be matched by a partial stable-set colouring that meets each path in the prescribed number of distinct colours?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3000006 (AMR-029-0006), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Egres Open - List of open problems, Open-problem page: Berge's conjecture on path partitions. Original source indexed by AMR-029-0006. https://oldlemon.cs.elte.hu/egres/open/List_of_open_problems.
• S3 EGRES Open, Berge's conjecture on path partitions. Individual source page and explanatory remarks. https://lemon.cs.elte.hu/egres/open/Berge%27s_conjecture_on_path_partitions.