Ortogonalidade entre empacotamento de caminhos e partições em conjuntos independentes para dígrafos bipartidos

Resumo

Em 1982, Berge propôs uma conjectura sobre grafos direcionados que relaciona partições em caminhos direcionados com coleções de conjuntos independentes disjuntos. Berge ainda mostrou que sua conjectura era válida para certas classes de grafos. Diante dos resultados por ele observados, é natural questionar-se se a relação continuaria a existir caso os papéis dos dois elementos -- caminhos e conjuntos independentes -- fossem invertidos. A questão natural que surge é então se há relação entre partições em conjuntos independentes (coloração) e coleções de caminhos direcionados. Essa relação ficou conhecida como versão dual da Conjectura de Berge. Dizemos que uma coloração $C$ e uma coleção de $k$ caminhos $P$, para um $k$ inteiro positivo, são \emph{ortogonais} se cada classe de cor de $C$ intersecta o maior número de caminhos possíveis em $P$, isto é, a intersecção é a classe toda se esta tem cardinalidade menos que $k$ ou $k$ caso contrário. Tal conjectura é falsa para digrafos em geral e apresenta contraexemplo. Entretanto, os contraexemplos conhecidos possuem ciclo ímpar e não há registro na literatura de ter sido pesquisado se a conjectura seria válida para dígrafos sem ciclos ímpares, isto é, digrafos bipartidos. Desse modo, este projeto pretende estudar de maneira mais aprofundada a relação entre coloração e coleções de caminhos, e verificar se a Conjectura Dual de Berge é verdadeira para digrafos bipartidos.