Coloração total em grafos K-caminho

Autores

  • Abel Rodolfo Garcia Lozano

Resumo

A coloração é uma sub-área que teve seu início com a conjectura das Quatro Cores, apresentada por Francis Guthrie a Augustus De Morgan, por volta de 1850 e provada por Appel e Haken, em 1977. As noções de coloração total e de número cromático total de um grafo foram introduzidas em 1965 simultaneamente por Behzad e Vizing, enquanto o conceito de grafo k-caminho surgiu no início da década de 70, através de Beineke e Pipert. A união destes conceitos, junto com a coloração de vértices com folga de ordem k, abordada pela primeira vez em 2009 por Lozano et all, formam o eixo principal deste artigo. Desta forma, este trabalho apoiado por dois teoremas e um corolário, mostra que todo grafo k-caminho satisfaz a conjectura de Vizing-Behzad para coloração total.

Downloads

Não há dados estatísticos.

Downloads

Publicado

2011-06-30

Como Citar

Lozano, A. R. G. (2011). Coloração total em grafos K-caminho. Revista Tecnologia, 32(1), 23–30. Recuperado de https://ojs.unifor.br/tec/article/view/4546

Edição

Seção

Artigos