Coloração total em grafos K-caminho

Abstract

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.