A proof for Berge's Dual Conjecture for Bipartite Digraphs

• Caroline Aparecida de Paula Silva Universidade Federal de São Carlos
• Cândida Nunes da Silva University of São Carlos at Sorocaba
• Orlando Lee Universidade Estadual de Campinas

Resumo

Dada uma coloração de vértices C = {C₁, C₂...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.

Palavras-chave: Conjectura Dual de Berge, Digrafos Bipartidos, Digrafos Perfeitos

Referências

Aharoni, R., Hartman, I. B.-A., and Hoffman, A. J. (1985). Path partitions and packs of acyclic digraphs. Pacific Journal of Mathematics, 2(118):249–259.

Berge, C. (1982a). Diperfect graphs. Combinatorica, 2(3):213–222.

Berge, C. (1982b). k-optimal Partitions of a Directed Graph. European Journal of Combinatorics, 3(2):97–101.

Chudnovsky, M., Robertson, N., Seymour, P., and Thomas, R. (2006). The strong perfect graph theorem. Annals of mathematics, pages 51–229.

Dilworth, R. P. (1950). A decomposition theorem for partially ordered sets. Annals of Mathematics, 51(1):161–166.

Gallai, T. (1959). Uber extreme punkt-und kantenmengen. Etvs Sect. Math, 2:133–138.

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

Gallai, T. and Milgram, A. N. (1960). Verallgemeinerung eines graphentheoretischen satzes von redei. Acta Sci Math, 21:181–186.

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

Hartman, I. B.-A., Saleh, F., and Hershkowitz, D. (1994). On greene’s theorem for digraphs. Journal of Graph Theory, 18(2):169–175.

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.

Rédei, L. (1934). Ein kombinatorischer satz. Acta Litt. Szeged, 7(39-43):97.

Roy, B. (1967). Nombre chromatique et plus longs chemins d’un graphe. ESAIM: Mathematical Modelling and Numerical Analysis-Modelisation Mathematique et Analyse Numerique, 1(5):129–132.

Silva, C. A. P., Silva, C. N., and Lee, O. (2019). A proof for Berge’s dual conjecture for bipartite digraphs. In Anais do IV Encontro de Teoria da Computacao, Porto Alegre, RS, Brasil. SBC.