08 abr 2022
14:00 Defesa de Mestrado Integralmente a distancia
Tema
Digrafos χ-Diperfeitos
Aluno
Caroline Aparecida de Paula Silva
Orientador / Docente
Orientador: Orlando Lee/ Coorientadora: Cândida Nunes da Silva
Breve resumo
Seja D um digrafo. Uma coloração C e um caminho P de D são ortogonais se P contém exatamente um vértice de cada classe de cor de C. Em 1982, Berge definiu a classe dos digrafos χ-diperfeitos. Um digrafo D é χ-diperfeito se para toda coloração mínima C de D, existe um caminho P ortogonal à C e essa propriedade vale para todo subdigrafo induzido de D. Berge mostrou que todo digrafo simétrico é χ-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 complemento de ciclo ímpar é χ-diperfeita. O objetivo final dessa área de pesquisa é obter uma caracterização dos digrafos χ-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-χ-diperfeitas de ciclos ímpares e seus complementos podem desempenhar um papel importante na caracterização dos digrafos χ-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 χ-diperfeitas. Nós também mostramos que digrafos in-semicompletos e digrafos arc in-semicompletos são χ-diperfeitos. Ademais, apresentamos novos exemplos de digrafos não-χ-diperfeitos minimais.
Banca examinadora
Titulares:
Orlando Lee IC/UNICAMP
Maycon Sambinelli CMCC/UFABC
Cláudio Leonardo Lucchesi IC/UNICAMP
Suplentes:
Guilherme Pimentel Telles IC/UNICAMP
Guilherme Oliveira Mota IME/USP