chi-Diperfect digraphs

Autor(es)

Caroline Aparecida de Paula Silva

• Tipo de documento: Dissertação de Mestrado
• Imprenta: Campinas, SP.
• Instituição: Universidade Estadual de Campinas (UNICAMP). Instituto de Computação
• Data de defesa: 2022-04-08

Membros da banca

Orlando Lee; Maycon Sambinelli; Cláudio Leonardo Lucchesi

• Orientador: Orlando Lee; Candida Nunes da Silva

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 (AU)

• Processo FAPESP: 20/06116-4 - Dígrafos chi-Diperfeitos
• Beneficiário: Caroline Aparecida de Paula Silva
• Modalidade de apoio: Bolsas no Brasil - Mestrado