Digrafos alpha-Diperfeitos e chi-Diperfeitos

• Processo: 22/03735-0
• Modalidade de apoio: Bolsas no Brasil - Doutorado
• Data de Início da vigência: 01 de dezembro de 2022
• Situação: Interrompido
• Área de 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
• Bolsa(s) vinculada(s): 23/16755-2 - Universalidade e madericidade de digrafos, BE.EP.DR
• Assunto(s): Teoria dos grafos
• Palavra(s)-Chave do Pesquisador: alpha-diperfect | chi-diperfect | digraphs | graphs | orthogonality | vertex coloring | Teoria dos Grafos

Resumo

Em 1982, Berge definiu duas classes de digrafos com o objetivo de identificar propriedades na relação entre conjuntos independentes e caminhos em digrafos. A primeira classe que Berge definiu é a classe dos digrafos $\alpha$-diperfeitos. Um digrafo $D$ é $\alpha$-diperfeito se todo subdigrafo $D'$ induzido de $D$ satisfaz a seguinte propriedade: para todo conjunto independente máximo de $D'$ existe uma partição em caminhos $\mathcal{P}$ de $D'$ tal que todo $P \in \mathcal{P}$ contém exatamente um vértice de $S$.A segunda classe que Berge definiu é a classe dos digrafos $\chi$-diperfeitos. Um digrafo $D$ é $\chi$-diperfeito se todo subdigrafo $D'$ induzido de $D$ satisfaz a seguinte propriedade: para toda coloração mínima $\mathcal{C}$ de $D'$ existe um caminho $P$ de $D'$ contendo exatamente um vértice de cada classe de cor de $\mathcal{C}$.O objetivo final dessa área de pesquisa é obter uma caracterização dos digrafos $\alpha$-diperfeito e dos digrafos $\chi$-diperfeitos em termos de subdigrafos induzidos probidos, mas esse parece ser um problema muito difícil e pouco provável de ser resolvido em um futuro próximo. Nesse projeto, pretendemos obter resultados em direção a esse objetivo por meio da investigação de propriedades estruturais dessas classes de digrafos e da análise de famílias específicas de digrafos para tentar descobrir quais elementos dessas famílias são $\alpha$-diperfeitos ou $\chi$-diperfeitos.