Empacotamento de caminhos e colorações parciais em digrafos.

• Processo: 24/14743-0
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de janeiro de 2025
• Data de Término da vigência: 31 de dezembro 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: Marcos Paulo Evers Cordeiro
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Assunto(s): Dígrafos Teoria dos grafos
• Palavra(s)-Chave do Pesquisador: Colorações parciais | Digrafos | Empacotamento de caminhos | teoria dos grafos | Teoria dos Grafos

Resumo

Neste projeto pretendemos estudar alguns problemas de natureza teórica. Para um digrafo arbitrário D, a relação entre partições em caminhos e empacotamentos de conjuntos estáveis (colorações parciais), assim como a relação entre partições em conjuntos estáveis (coloração) e empacotamento de caminhos ainda não é completamente entendida. Duas conjecturas de Linial tentam capturar essas duas relações, respectivamente. O projeto pretende focar no segundo problema, mas apresentamos ambos os problemas pois estão estreitamente relacionados por uma relação de dualidade.