En teoría de grafos, una coloración total es un tipo de coloración de los vértices y bordes de un gráfico. A menos que se indique explícitamente lo contrario, se supone que una coloración total es correcta en el sentido de que no se colorean con el mismo color los vértices adyacentes ni las aristas adyacentes y los vértices que se encuentran en los extremos de las aristas.
El número cromático total χ″( G ) de un gráfico G es el menor número de colores necesarios para una coloración total de G .
Un grafo total T = T( G ) de un grafo G es un grafo en el que
Con esta definición, una coloración total se convierte en una coloración de vértice (adecuada) de un gráfico total.
Varias propiedades de χ″( G ):
Aquí Δ( G ) es la potencia máxima de , y ch′( G ) es el índice de la coloración de borde prescrita .
La coloración total surge de forma natural, ya que es una simple mezcla de coloraciones de vértice y borde. El siguiente paso es considerar los límites superiores del número cromático total en términos del grado máximo, por analogía con los teoremas de Brooks o Vizing . Resultó que determinar los límites superiores de una coloración total en función del grado máximo es una tarea difícil y ha eludido a los matemáticos durante 40 años.
La conjetura más famosa dice así:
Conjetura sobre la coloración total.
χ″( G ) ≤ Δ( G ) + 2.Aparentemente, el término "coloración total" y la formulación de la conjetura fueron propuestos de forma independiente por Behzad y Vizing en numerosas publicaciones entre 1964 y 1968 (ver el libro de Jensen y Toft [3] para más detalles).
Se sabe que la conjetura se cumple para varias clases importantes de gráficos, como los gráficos bipartitos y la mayoría de los gráficos planos , con la excepción de los gráficos con un grado máximo de 6. El caso de los gráficos planos se resolverá si la conjetura del gráfico plano de Vizing es resultó ser cierto. Además, si la conjetura sobre el color de borde prescrito es verdadera, entonces χ″( G ) ≤ Δ( G ) + 3.
Se han obtenido algunos resultados con respecto a la coloración total. Por ejemplo, Kylakos y Read [4] demostraron que el índice cromático fraccionario del grafo total para un grafo G no excede Δ( G ) + 2.
También mencionamos la siguiente conexión entre el gráfico de líneas y el gráfico total :
T ( G ) es Euler si y sólo si L ( G ) es Euler .