Busca avançada
Ano de início
Entree

Dígrafos chi-Diperfeitos

Processo: 20/06116-4
Linha de fomento:Bolsas no Brasil - Mestrado
Vigência (Início): 01 de janeiro de 2021
Vigência (Término): 28 de fevereiro de 2022
Área do conhecimento:Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
Pesquisador responsável:Orlando Lee
Beneficiário:Caroline Aparecida de Paula Silva
Instituição-sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
Vinculado ao auxílio:15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural, AP.TEM
Assunto(s):Teoria dos grafos   Dígrafos   Vértices

Resumo

Seja $D$ um dígrafo. 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 dígrafos $\chi$-diperfeitos. Um dígrafo $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 subdígrafo induzido de $D$. Berge também mostrou que todo dígrafo perfeito é $\chi$-diperfeito, assim como todo dígrafo 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 subdígrafo $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 dígrafo $\chi$-diperfeito não pode conter um ciclo ímpar conflitante como subdígrafo 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 dígrafos $\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 dígrafos para tentar descobrir quais elementos de tais classes são $\chi$-diperfeitos. (AU)