Famílias Consistentes e a Coloração Total de Grafos

Abstract

Neste trabalho apresentamos o conceito de famílias consistentes e alguns resultados teóricos, com o objetivo principal de desenvolver uma heurística para a coloração total de grafos, procurando respeitar a conjectura de Vizing-Behzad. Para isso, definimos inicialmente alguns termos necessários para a identificação destas famílias. Em seguida, provamos quatro proposições relativas a este novo conceito, e finalizamos o texto fazendo a conexão entre estas famílias e a coloração total.