| Processo: | 22/03735-0 |
| Modalidade de apoio: | Bolsas no Brasil - Doutorado |
| Data de Início da vigência: | 01 de dezembro de 2022 |
| Data de Término da vigência: | 28 de fevereiro de 2027 |
| Á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. | |
| Matéria(s) publicada(s) na Agência FAPESP sobre a bolsa: | |
| Mais itensMenos itens | |
| TITULO | |
| Matéria(s) publicada(s) em Outras Mídias ( ): | |
| Mais itensMenos itens | |
| VEICULO: TITULO (DATA) | |
| VEICULO: TITULO (DATA) | |