O problema da interseção de caminhos mais longos em classes de grafos
| Processo: | 12/16418-1 |
| Modalidade de apoio: | Bolsas no Exterior - Estágio de Pesquisa - Mestrado |
| Data de Início da vigência: | 01 de outubro de 2012 |
| Data de Término da vigência: | 31 de março de 2013 |
| Área de conhecimento: | Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação |
| Pesquisador responsável: | Celia Picinin de Mello |
| Beneficiário: | Atilio Gomes Luiz |
| Supervisor: | R. Bruce Richter |
| Instituição Sede: | Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil |
| Instituição Anfitriã: | University of Waterloo, Canadá |
| Vinculado à bolsa: | 12/10562-3 - Coloração total semiforte, BP.MS |
| Assunto(s): | Teoria dos grafos Matemática da computação |
| Palavra(s)-Chave do Pesquisador: | Coloração de grafos | Conjetura de Albertson | Crossing number | Número cromático | Teoria dos Grafos |
Resumo Este projeto de pesquisa é parte da solicitação de uma bolsa de estágio no exterior para Atílio Gomes Luiz, vinculado ao processo 2012/105623. Propõe-se a investigação da conjetura de Albertson, que relaciona o número cromático e o número de cruzamentos (crossing number) de um grafo. Em 2007, Michael Albertson conjeturou que se um grafo G possui número cromático igual a r, então o número de cruzamentos de G é maior ou igual ao número de cruzamentos do grafo completo com r vértices. Esta conjetura foi provada para r menor ou igual a 16 e continua aberta para os demais casos. O objetivo deste projeto é investigar esta conjetura para algumas classes de grafos. (AU) | |
| 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) | |