Coloración total
En la teoría de grafos , la coloración total es un tipo de coloración de gráficos en los vértices y bordes de un gráfico. 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 ningún borde adyacente, ningún vértice adyacente y ningún borde ni 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 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 sólo 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 (propia) de T ( G ). Una coloración total es una partición de los vértices y las aristas del gráfico en conjuntos independientes totales .
La coloración total surge naturalmente 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, Behzad y Vizing introdujeron de forma independiente el término "coloración total" y la afirmación de la conjetura de coloración total en numerosas ocasiones entre 1964 y 1968 (ver Jensen & Toft). Se sabe que la conjetura se cumple para algunas clases importantes de gráficos, como todos los gráficos bipartitos y la mayoría de los gráficos planos, excepto aquellos con un grado máximo de 6. El caso plano se puede completar si la conjetura del gráfico plano de Vizing es verdadera. Además, si la conjetura de colorear 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 fraccionario del grafo total de un grafo G es como máximo Δ( G ) + 2.
