A proof for Berges Dual Conjecture for Bipartite Digraphs
Resumo
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.
Referências
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.
