Coloración total
En teoría de grafos , la coloración total es un tipo de coloración de grafos en los vértices y aristas de una gráfica. Cuando se usa sin ninguna calificación, siempre se asume que una coloración total es adecuada en el sentido de que no se asigna el mismo color a los bordes adyacentes, ni a los vértices adyacentes, ni a los bordes ni a ningún vértice final. El número cromático total χ ″ ( G ) de un gráfico G es la menor cantidad de colores necesarios en cualquier coloración total de G.
El gráfico total T = T ( G ) de un gráfico G es un gráfico 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 correspondientes los elementos son adyacentes o incidentes en G. Entonces la coloración total de G se convierte en una coloración de vértice (adecuada) de T ( G ). Una coloración total es una partición de los vértices y los bordes del gráfico en conjuntos independientes totales .
La coloración total surge de forma natural, ya que es simplemente una mezcla de coloraciones de vértice y borde. El siguiente paso es buscar cualquier límite superior tipo Brooks o 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 la 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 gráficas, como todas las gráficas bipartitas y la mayoría de las gráficas planas, excepto aquellas con grado máximo 6. El caso planar puede completarse si la conjetura de la gráfica planar de Vizing es verdadera. Además, si la conjetura del color de la lista es cierta, entonces
Se han obtenido resultados relacionados con la coloración total. Por ejemplo, Kilakos y Reed (1993) demostraron que el número cromático fraccional del gráfico total de un gráfico G es como máximo Δ ( G ) + 2.
