A proof for Berges Dual Conjecture for Bipartite Digraphs

  • Caroline Silva UFSCAR
  • Cândida Silva UFSCAR
  • Orlando Lee UNICAMP


Given a (vertex)-coloring C = C 1 , C 2 , ...C m of P a digraph D and a positive integer k, the k-norm of C is defined as C k = m i=1 min C i, k. A coloring C is k-optimal if its k-norm C k is minimum over all colorings. A (path) k-pack P k is a collection of at most k vertex-disjoint paths. A coloring C and a k-pack P k are orthogonal if each color class intersects as many paths as possible in P k , that is, if C i k, C i P j = 1 for every path P j P k , otherwise each vertex of C i lies in a different path of P k . In 1982, Berge conjectured that for every k-optimal coloring C there is a k-pack P k orthogonal to C. This conjecture is false for arbitrary digraphs, having a counterexample with odd cycle. In this paper we prove this conjecture for bipartite digraphs.

Palavras-chave: Berges Dual Conjecture, Bipartite Digraphs


Berge, C. (1982). k-optimal Partitions of a Directed Graph. European Journal ofCombi- natorics, 3(2):97–101.
Gallai, T. (1959). U¨ ber extreme punkt-und kantenmengen. Etvs Sect. Math, 2:133–138.

Gallai, T. (1968). On directed paths and circuits. Theory ofgraphs, pages 115–118.

Greene, C. (1976). Some partitions associated with a partially ordered set. Journal of Combinatorial Theory, Series A, 20(1):69–79.

Hartman, I. B.-A. (2006). Berge’s conjecture on directed path partitions—a survey. Dis- crete Mathematics, 306(19–20):2498–2514.

Konig, D. (1931). Graphen und Matrizen. Matematikai Lapok, 38:116–119.

Linial, N. (1981). Extending the Greene-Kleitman theorem to directed graphs. Journal of Combinatorial Theory, Series A, 30(3):331–334.

Mirsky, L. (1971). A dual of Dilworth’s decomposition theorem. Amer. Math. Monthly, 78:876–877.

Roy, B. (1967). Nombre chromatique et plus longs chemins d’un graphe. ESAIM: Math- ematical Modelling and Numerical Analysis-Modelisation Mathematique et Analyse Numerique, 1(5):129–132.
SILVA, Caroline; SILVA, Cândida ; LEE, Orlando . A proof for Berges Dual Conjecture for Bipartite Digraphs. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 4. , 2019, Belém. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2019 . ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2019.6398.