Digrafos chi-Diperfeitos

Resumo

Seja $D$ um digrafo. Uma coloração $\cal{C}$ e um caminho $P$ de $D$ são \emph{ortogonais} se $P$ contém exatamente um vértice de cada classe de cor em $\cal{C}$. Em 1982, Berge definiu a classe de digrafos $\chi$-diperfeitos. Um digrafo $D$ é $\chi$-diperfeito se para toda coloração ótima $\cal{C}$ de $D$, existe um caminho $P$ ortogonal a $C$ e essa propriedade é válida para todo subdigrafo induzido de $D$. Berge também mostrou que todo digrafo perfeito é $\chi$-diperfeito, assim como todo digrafo simétrico.Seja $D$ uma super-orientação de um ciclo ímpar $C=(x_1,x_2,\ldots,x_{2\ell+1},x_1)$ e seja $P=(x_i,\ldots,x_j)$ um caminho de $C$. O subdigrafo $D[V(P)]$ é um \emph{setor} se $x_i$ e $x_j$ são fontes ou sorvedouros em $D$; um setor é \emph{ímpar} se $P$ tem comprimento ímpar. Dizemos que $D$ é um \emph{ciclo ímpar conflitante} se contém pelo menos dois setores arco-disjuntos. É possível demonstrar que uma orientação de um ciclo ímpar é $\chi$-diperfeita, se e somente se, não é um ciclo ímpar conflitante. A partir disso, temos que um digrafo $\chi$-diperfeito não pode conter um ciclo ímpar conflitante como subdigrafo induzido. O inverso, entretanto, não é verdadeiro; Berge mostrou que existe orientação do complemento de um ciclo ímpar com sete vértices que não possui cíclo ímpar conflitante induzido e não é $\chi$-diperfeito. É desejável que se obtenha uma caracterização de digrafos $\chi$-diperfeitos, mas esse é um problema muito difícil e não é muito provável que seja resolvido em um futuro próximo. Nesse projeto, pretendemos começar a investigar esse problema através de duas abordagens. A primeira é a tentativa de encontrar uma caracterização de quais orientações de complemento de ciclos ímpares são $\chi$-diperfeitas. A segunda é considerar algumas classes específicas de digrafos para tentar descobrir quais elementos de tais classes são $\chi$-diperfeitos.