A proof for Berge’s Dual Conjecture for Bipartite Digraphs

Autores

  • Orlando Lee Universidade Estadual de Campinas
  • Cândida Silva Universidade Federal de São Carlos, campus Sorocaba/SP
  • Caroline Silva Universidade Federal de São Carlos, campus Sorocaba/SP

DOI:

https://doi.org/10.5753/reic.2020.1743

Resumo

Given a (vertex)-coloring $\mathcal{C} = \{C_{1}, C_{2}, ... C_{m}\}$ of a digraph $D$ and a positive integer $k$, the $k$-norm of $\mathcal{C}$ is defined as  $ |\mathcal{C}|_k = \sum_{i = 1}^{m} min\{|C_i|, k\}.$ A coloring $\mathcal{C}$ is $k$-optimal if its $k$-norm  $|\mathcal{C}|_k$ is minimum over all colorings. A (path) $k$-pack  $\mathcal{P}^k$ is a collection of at most $k$ vertex-disjoint paths. A coloring $\mathcal{C}$ and a $k$-pack $\mathcal{P}^k$ are orthogonal if each color class intersects as many paths as possible in $\mathcal{P}^k$, that is, if $|C_i| \ge k$, $|C_i \cap P_j| = 1$ for every path $P_j \in \mathcal{P}^k$, otherwise each vertex of $C_i$ lies in a different path of $\mathcal{P}^k$. In 1982, Berge conjectured that for every $k$-optimal coloring $\mathcal{C}$ there is a $k$-pack $\mathcal{P}^k$ orthogonal to $\mathcal{C}$. This conjecture is false for arbitrary digraphs, having a counterexample with odd cycle. In this paper we prove this conjecture for bipartite digraphs. In addition we show that the conjecture cannot hold for perfect graphs by exhibiting a counterexample.

Downloads

Não há dados estatísticos.

Downloads

Publicado

2020-11-15

Como Citar

Lee, O., Silva, C., & Silva, C. (2020). A proof for Berge’s Dual Conjecture for Bipartite Digraphs. Revista Eletrônica De Iniciação Científica Em Computação, 18(3). https://doi.org/10.5753/reic.2020.1743