A proof for Berge's Dual Conjecture for Bipartite Digraphs - Silva, Caroline Aparecida de Paula; da Silva, Cândida Nunes; Lee, Orlando (Anais do Concurso de Trabalhos de Iniciação Científica da SBC (CTIC-SBC), 2020)
Dada uma coloração de vértices C = {C 1 , C 2 ...C m } de um digrafo D e um inteiro positivo k, a k-norma de C é definida como |C| k = ∑ i=1 m min {|C i |, k}.Uma coloração C é k-ótima se sua k-norma |C| k é mínima dentre todas as colorações. Um k-sistema de caminhos P k é uma coleção de, no máximo, k caminhos vértice-disjuntos. Uma coloração C e um k-sistema de caminhos P k são ortogonais se cada classe de cor intersecta o maior número de caminhos possíveis de P k , isto é, se |C i | ≥ k, |C i ⋂ P j | = 1 para todo caminho P j ∊ P k , caso contrário, cada vértice de C i está em um caminho diferente de P k . Em 1982, Berge conjecturou que para toda coloração k-ótima C existe um k-sistema de caminhos P k ortogonal à C. Essa conjectura é falsa no caso geral, tendo um contraexemplo com ciclo ímpar. Nesse artigo, provaremos essa conjectura para digrafos bipartidos. Ainda, mostramos que essa conjectura não é válida para grafos perfeitos, exibindo um contraexemplo.