Coloração de arestas em grafos indiferença

AUTOR(ES)

Flavio de Freitas Stecca

DATA DE PUBLICAÇÃO

2003

RESUMO

Esta dissertação aborda o problema da coloração de arestas restrito aos grafos indiferença. O teorema de Vizing diz que qualquer grafo pode ter suas arestas coloridas com .6 (G) ou .6( G) + 1 cores. Grafos pertencentes à Classe 1 são os grafos cujo índice cromático (n úmero mínimo de cores suficientes para pintar suas arestas) X é igual a .6 ( G) . Se X = .6(G) + 1, o grafo pertence à Classe 2. Um grafo é dito overfull se .6(G) l_J

ASSUNTO(S)

programação linear teoria dos grafos teoria da computação

Documentos Relacionados

• Coloração de arestas em grafos split
• Caracterização e coloração de arestas para cografos
• Grafos Associados aos Emparelhamentos de Arestas de Polígonos Regulares
• Implementação e análise de algoritmos para coloração de arestas
• Alocação estruturada de registradores atraves de coloração de grafos