En teoría de grafos , la coloración total es un tipo de coloración de los vértices y aristas de un grafo. Cuando se utiliza sin ninguna calificación, siempre se supone que una coloración total es adecuada en el sentido de que ninguna arista adyacente, ningún vértice adyacente y ninguna arista y ningún vértice final reciben el mismo color. El número cromático total χ″( G ) de un grafo G es la menor cantidad de colores necesarios en cualquier coloración total de G .
El grafo total T = T ( G ) de un grafo G es un grafo tal que (i) el conjunto de vértices de T corresponde a los vértices y aristas de G y (ii) dos vértices son adyacentes en T si y solo si sus elementos correspondientes son adyacentes o incidentes en G . Entonces la coloración total de G se convierte en una coloración de vértice (propia) de T ( G ). Una coloración total es una partición de los vértices y aristas del grafo en conjuntos totales independientes.
Algunas desigualdades para χ″( G ):
Aquí Δ( G ) es el grado máximo ; y ch′( G ), la posibilidad de elección de aristas .
La coloración total surge de manera natural, ya que es simplemente una mezcla de coloraciones de vértices y aristas. El siguiente paso es buscar cualquier límite superior de tipo Brooks o de tipo Vizing en el número cromático total en términos de grado máximo.
La versión de coloración total del límite superior de grado máximo es un problema difícil que ha eludido a los matemáticos durante 50 años. Un límite inferior trivial para χ″( G ) es Δ( G ) + 1. Algunos gráficos, como los ciclos de longitud y los gráficos bipartitos completos de la forma, necesitan Δ( G ) + 2 colores, pero no se ha encontrado ningún gráfico que requiera más colores. Esto lleva a la especulación de que cada gráfico necesita Δ( G ) + 1 o Δ( G ) + 2 colores, pero nunca más:
Aparentemente, el término "coloración total" y el enunciado de la conjetura de coloración total fueron introducidos independientemente por Behzad y Vizing en numerosas ocasiones entre 1964 y 1968 (ver Jensen y Toft). Se sabe que la conjetura es válida para algunas clases importantes de grafos, como todos los grafos bipartitos y la mayoría de los grafos planares excepto aquellos con grado máximo 6. El caso planar puede completarse si la conjetura de grafos planares de Vizing es verdadera. Además, si la conjetura de coloración de listas es verdadera, entonces
Se han obtenido resultados relacionados con la coloración total. Por ejemplo, Kilakos y Reed (1993) demostraron que el número cromático fraccionario del grafo total de un grafo G es como máximo Δ( G ) + 2.
