Universalidade e madericidade de digrafos

• Processo: 23/16755-2
• Modalidade de apoio: Bolsas no Exterior - Estágio de Pesquisa - Doutorado
• Data de Início da vigência: 01 de setembro de 2024
• Data de Término da vigência: 31 de agosto de 2025
• Á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
• Supervisor: Frederic Havet
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Instituição Anfitriã: Institut National de Recherche en Informatique et en Automatique (INRIA Sophia Antipolis), França
• Vinculado à bolsa: 22/03735-0 - Digrafos alpha-Diperfeitos e chi-Diperfeitos, BP.DR
• Assunto(s): Coloração Dígrafos Grafos
• Palavra(s)-Chave do Pesquisador: coloração | Digrafos | grafos | Combinatória; Teoria dos Grafos;

Resumo

Em problemas de universalidade e madericidade de digrafos, estamos interessados em obter condições suficientes para um digrafo conter uma certa subestrutura fixa. Formalmente, para um parâmetro $\gamma$ de um digrafo, dizemos que um digrafo $F$ é $\gamma$-universal se existe um inteiro $c = c(F)$ tal que todo digrafo $D$ com $\gamma(D) \geq c$ contém $F$ como subdigrafo. Similarmente, dizemos que um digrafo $F$ é $\gamma$-maderiano se existe um inteiro $c = c(F)$ tal que todo digrafo $D$ com $\gamma(D) \geq c$ contém uma subdivisão de $F$ como subdigrafo.Muitos estudos têm sido realizados sobre universalidade e madericidade de digrafos, por exemplo quando $\gamma$ é o número cromático, grau mínimo de saída, grau médio de saída, etc. Aqui, estamos particularmente interessados quando $\gamma$ é o número cromático $\chi$. Sabe-se que um digrafo $F$ é $\chi$-universal (respectivamente, $\chi$-maderiano) se e somente se $F$ é uma orientação de uma floresta. Entretanto, é um problema em aberto determinar qual o menor $c$ para o qual todo digrafo $D$ com $\chi(D) \geq c$ contém uma árvore orientada $F$ como subdigrafo (respectivamente, como uma subdivisão); tal valor $c$ é chamado de $\chi$-universalidade de $F$ (respectivamente, $\chi$-madericidade de $F$). O melhor limitante superior conhecido até então para esses parâmetros é quadrático na ordem de $F$, mas esse valor não é justo. Nesse projeto, pretendemos investigar esses problemas com o objetivo de obter limitantes superiores mais justos para a $\chi$-universalidade e para a $\chi$-madericidade de uma árvore orientada.