Coloración total

Problema sin resolver en matemáticas

Conjetura:${\displaystyle \chi ''(G)\leq \Delta (G)+2.}$

Más problemas sin resolver en matemáticas

En teoría de grafos , la coloración total es un tipo de coloración de grafos aplicada a los vértices y aristas de un grafo. Cuando se utiliza sin ninguna especificación, se asume que una coloración total es propia , en el sentido de que ninguna arista adyacente, ningún vértice adyacente y ninguna arista y vértice extremo tienen asignado el mismo color. El número cromático total χ ″( G ) de un grafo G es el número mínimo 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értices (propia) de T ( G ) . Una coloración total es una partición de los vértices y aristas del grafo en conjuntos independientes totales .

Algunas desigualdades para χ ″( G ) :

1. ${\displaystyle \chi ''(G)\geq \Delta (G)+1.}$
2. ${\displaystyle \chi ''(G)\leq \Delta (G)+10^{26}.}$ (Molloy, Reed 1998)
3. ${\displaystyle \chi ''(G)\leq \Delta (G)+8\ln ^{8}(\Delta (G))}$para Δ ( G ) suficientemente grande . (Hind, Molloy, Reed 1998)
4. ${\displaystyle \chi ''(G)\leq \operatorname {ch} '(G)+2.}$

Aquí Δ( G ) es el grado máximo ; y ch′( G ) , la elegibilidad de la arista .

La coloración total surge de forma natural, ya que es simplemente una combinación de coloraciones de vértices y aristas. El siguiente paso consiste en buscar cualquier límite superior, del tipo Brooks o Vizing , para el número cromático total en términos de grado máximo.

La versión de coloración total del límite superior del 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 grafos como ciclos de longitud${\displaystyle n\not \equiv 0{\bmod {3}}}$y los grafos bipartitos completos de la forma K _n,n necesitan Δ( G ) + 2 colores, pero no se ha encontrado ningún grafo que requiera más colores. Esto lleva a la especulación de que cada grafo necesita Δ( G ) + 1 o Δ( G ) + 2 colores, pero nunca más:

Conjetura de coloración total ( Behzad , Vizing).${\displaystyle \chi ''(G)\leq \Delta (G)+2.}$

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 (véase Jensen y Toft). Se sabe que la conjetura se cumple 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 se puede completar si la conjetura de grafos planares de Vizing es verdadera. Además, si la conjetura de coloración de listas es verdadera, entonces${\displaystyle \chi ''(G)\leq \Delta (G)+3.}$

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 grafo total de un grafo G es como máximo Δ( G ) + 2 .

• Hind, Hugh; Molloy, Michael; Reed, Bruce (1998). "Coloración total con Δ + poli(log Δ) colores". SIAM Journal on Computing . 28 (3): 816– 821. doi : 10.1137/S0097539795294578 .
• Jensen, Tommy R.; Toft, Bjarne (1995). Problemas de coloración de grafos . Nueva York: Wiley-Interscience. ISBN 0-471-02865-7.
• Kilakos, Kyriakos; Reed, Bruce (1993). "Coloración fraccionaria de grafos totales". Combinatorica . 13 (4): 435– 440. doi : 10.1007/BF01303515 . S2CID 31163141 . 
• Molloy, Michael; Reed, Bruce (1998). "Una cota para el número cromático total". Combinatorica . 18 (2): 241– 280. doi : 10.1007/PL00009820 . hdl : 1807/9465 . S2CID 9600550 .