Aspectos teoricos, estruturais e de otimizacao de alguns problemas em grafos.
Bruce Reed | Centre National de la Recherche Scientifique - França
Processo: | 12/10562-3 |
Modalidade de apoio: | Bolsas no Brasil - Mestrado |
Vigência (Início): | 01 de agosto de 2012 |
Vigência (Término): | 31 de janeiro de 2014 |
Área do 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 |
Instituição Sede: | Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil |
Bolsa(s) vinculada(s): | 12/16418-1 - Conjetura de Albertson, BE.EP.MS |
Assunto(s): | Teoria dos grafos |
Palavra(s)-Chave do Pesquisador: | Coloração em Grafos | coloração total em grafos | coloração total semiforte em grafos | Grafos equipartidos completos | Teoria dos grafos |
Resumo Este é um projeto de pesquisa para a solicitação de uma bolsa de mestrado para Atílio Gomes Luiz. Propõe-se a investigação de um tipo especial de coloração total, denominada coloração total semiforte. Dada uma coloração total, rotula-se cada vértice do grafo com o conjunto formado pela cor do vértice e pelas cores das arestas que nele incidem. Uma coloração total é semiforte quando os rótulos de vértices adjacentes são distintos. O menor número de cores para o qual um grafo admite uma coloração total semiforte é denominado número cromático total semiforte. Pouco se conhece sobre o problema de se determinar o número cromático total semiforte: está determinado para poucas famílias de grafos, mas a complexidade do problema é desconhecida. No artigo seminal desta coloração, os autores conjeturam que o número cromático total semiforte de um grafo simples é no máximo o seu grau máximo mais três unidades. Neste projeto, pretendemos verificar a conjetura citada para os grafos de algumas classes e, se possível, determinar o número cromático total semiforte desses grafos. | |
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) | |