chi-Diperfect digraphs = Digrafos chi-diperfeitos

Caroline Aparecida de Paula Silva

chi-Diperfect digraphs [recurso eletrônico] = Digrafos chi-diperfeitos

Caroline Aparecida de Paula Silva

Material

DISSERTAÇÃO

Idioma

Inglês

Número de chamada

T/UNICAMP Si38c

Título paralelo/equiv.

[Digrafos chi-diperfeitos]

Publicação

Campinas, SP : [s.n.], 2022.

Descrição física

1 recurso online (60 p.) : il., digital, arquivo PDF.

Nota geral

Orientadores: Orlando Lee, Cândida Nunes da Silva

Nota de dissertação ou tese

Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação

Resumo Resumo: Seja D um digrafo. Uma coloração S e um caminho P de D são ortogonais se P contém exatamente um vértice de cada classe de cor de S. Em 1982, Berge definiu a classe dos digrafos chi-diperfeitos. Um digrafo D é chi-diperfeito se para toda coloração mínima S de D, existe um caminho P ortogonal... Ver mais Resumo: Seja D um digrafo. Uma coloração S e um caminho P de D são ortogonais se P contém exatamente um vértice de cada classe de cor de S. Em 1982, Berge definiu a classe dos digrafos chi-diperfeitos. Um digrafo D é chi-diperfeito se para toda coloração mínima S de D, existe um caminho P ortogonal à S e essa propriedade vale para todo subdigrafo induzido de D. Berge mostrou que todo digrafo simétrico é chi-diperfeito, bem como todo digrafo cujo grafo subjacente é perfeito. Entretanto, ele também mostrou que nem toda super-orientação de um ciclo ímpar ou do complemento de ciclo ímpar é chi-diperfeita. O objetivo final dessa área de pesquisa é obter uma caracterização dos digrafos chi-diperfeitos em termos de subdigrafos induzidos proibidos, mas esse parece ser um problema muito difícil e pouco provável de ser resolvido em um futuro próximo. Super-orientações não-chi-diperfeitas de ciclos ímpares e seus complementos podem desempenhar um papel importante na caracterização dos digrafos chi-diperfeitos, de forma semelhante ao papel que desempenham na caracterização de grafos perfeitos. Nessa dissertação, nós apresentamos uma caracterização de super-orientações de ciclos ímpares e uma caracterização de super-orientações de complemento de ciclos ímpares que são chi-diperfeitas. Nós também mostramos que digrafos localmente in-semicompletos e digrafos localmente arco in-semicompletos são chi-diperfeitos. Ademais, apresentamos exemplos de digrafos não-chi-diperfeitos minimais que ainda não eram conhecidos Ver menos

Abstract: Let D be a digraph. A coloring S and a path P of D are orthogonal if P contains exactly one vertex of each color class in S. In 1982, Berge defined the class of chi-diperfect digraphs. A digraph D is chi-diperfect if for every minimum coloring S of D, there exists a path P orthogonal to S... Ver mais Abstract: Let D be a digraph. A coloring S and a path P of D are orthogonal if P contains exactly one vertex of each color class in S. In 1982, Berge defined the class of chi-diperfect digraphs. A digraph D is chi-diperfect if for every minimum coloring S of D, there exists a path P orthogonal to S and this property holds for every induced subdigraph of D. Berge showed that every symmetric digraph is chi-diperfect, as well as every digraph whose underlying graph is perfect. However, he also showed that not every super-orientation of an odd cycle or the complement of an odd cycle is chi-diperfect. The ultimate goal of this research area would be to obtain a characterization of chi-diperfect digraphs in terms of forbidden subdigraphs, but this may be a very difficult problem and not likely to be solved in a near future. Non-chi-diperfect super-orientations of odd cycles and their complements may play an important role in the characterization of chi-diperfect digraphs, similarly to the role they play in the characterization of perfect graphs. In this dissertation, we present a characterization of super-orientations of odd cycles and a characterization of super-orientations of complements of odd cycles that are chi-diperfect. We also show that locally in-semicomplete digraphs and locally arc in-semicomplete digraphs are chi-diperfect. Furthermore, we present some examples of minimal non-chi-diperfect digraphs which were not known yet Ver menos

Nota de sistema

Requisitos do sistema: Software para leitura de arquivo em PDF

Assuntos

Teoria dos grafos

Coloração de grafos

Grafos orientados

Autoria

Silva, Caroline Aparecida de Paula, 1998-

Lee, Orlando, 1969- Orientador

Silva, Candida Nunes da Coorientador

Sambinelli, Maycon, 1988- Avaliador

Lucchesi, Cláudio Leonardo, 1945- Avaliador