Coloración de grafos

La vértice coloración (o simplemente coloración) es la asignación de los vértices de un grafo con colores tal que dos vértices que compartan la misma arista tengan colores diferentes. Un grafo con bucles no puede ser coloreado, y solo se consideran grafos simples.

La terminología de usar colores para etiquetar vértices proviene del problema de colorear mapas. Las etiquetas como rojo o azul son solamente utilizadas cuando el número de colores es pequeño, y normalmente los colores están representados por los enteros {1, 2, 3, …}.

Una coloración que usa a lo más k colores se llama k-coloración (propia). El menor número de colores necesarios para colorear un grafo G se llama número cromático y se denota como χ(G). Un grafo que puede ser asignada una k-coloración (propia) es k-coloreable y es k-cromático si su número cromático es exactamente k. Un subconjunto de vértices asignados con el mismo color se llama una clase de color. Cada clase forma un conjunto independiente. Esto es, una k-coloración es lo mismo que una partición del conjunto de vértices en k conjuntos independientes, y los términos k-partito y k-coloreable tienen el mismo significado.

El polinomio cromático cuenta el número de maneras en las cuales puede ser coloreado un grafo usando no más que un número de colores dado. Por ejemplo, usando 3 colores, el grafo en la imagen de la derecha puede ser coloreado de 12 formas distintas. Con solo 2 colores, no puede ser coloreado. Con 4 colores, puede ser coloreado de 24+4*12 maneras distintas: usando los cuatro colores juntos, hay 4!= 24 coloraciones válidas (toda asignación de cuatro colores a algún grafo de cuatro vértices es una coloración propia); y para cada elección de tres de los cuatro colores, hay 12 3-coloraciones válidas. Así que, para el grafo del ejemplo, una tabla de números de coloraciones válidas puede comenzar como esta:

El polinomio cromático es una función p(G, t) que cuenta el número de t-coloraciones de G. como el nombre lo indica para un grafo G la función es un polinomio en t. para el grafo del ejemplo, P(G, t)= t(t-1)^2 (t-2) y P(G,4)=72

Polinomios cromáticos de algunos grafos.

Triángulo K3	${\displaystyle t(t-1)(t-2)\,}$
Grafo completo Kn	${\displaystyle t(t-1)(t-2)\cdots (t-(n-1))\,}$
Árbol con n vértices	${\displaystyle t(t-1)^{n-1}\,}$
Ciclo Cn	${\displaystyle (t-1)^{n}+(-1)^{n}(t-1)\,}$
Grafo de Petersen	${\displaystyle t(t-1)(t-2)(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t-352)\,}$

Una arista coloración de un grafo, es una coloración de las aristas, denotada como la asignación de colores a aristas tal que aristas incidentes tengan un color distinto. Una arista coloración con k colores es llamada k-arista-coloración y es equivalente al problema de particionar el conjunto de aristas en k emparejamientos. El menor número de colores necesarios para un arista coloración de un grafo G es el índice cromático o número cromático de aristas. Una coloración Tait es una 3-arista-coloración de un grafo cúbico. El teorema de los cuatro colores es equivalente a que cada grafo cúbico sin puentes admite una coloración Tait.

Asignando distintos colores a distintos vértices siempre obtendremos una coloración propia, entonces

${\displaystyle 1\leq \chi (G)\leq n.\,}$

El único grafo que es 1-coloreable es el grafo sin aristas, y el grafo completo ${\displaystyle K_{n}\,}$ de n vértices requiere ${\displaystyle \chi (K_{n})=n\,}$ colores.

Si G contiene un clique de orden k, entonces a lo menos son necesarios k colores para colorear el clique; en otras palabras, el número cromático es a los menos el número de clique:

${\displaystyle \chi (G)\geq \omega (G).\,}$

Los grafos 2-coloreables son exactamente grafos bipartitos, incluidos árboles y bosques. Por el teorema de los cuatro colores, todo grafo plano es 4-coloreable.

La arista coloración es una vértice coloración de su grafo lineal, y viceversa. Esto es,

${\displaystyle \chi '(G)=\chi (L(G)).\,}$

Existe una fuerte relación entre la arista coloración y el grado máximo del grafo. Como todas las aristas incidentes a algún vértice necesitan colores distintos, tenemos

${\displaystyle \chi '(G)\geq \Delta (G).\,}$

Más aún,

Teorema de König: Si ${\displaystyle G\,}$ es bipartito entonces ${\displaystyle \chi '(G)=\Delta (G)\,}$

Teorema de Vizing (1964): ${\displaystyle \chi '(G)\leq \Delta (G)+1.\,}$

Una importante clase de problemas de coloreado impropias es estudiada en teoría de Ramsey, en donde se asignan colores a las aristas del grafo, y no hay restricción sobre los colores en aristas incidentes. Un ejemplo simple es el teorema de la amistad que nos dice que en toda 2-arista-coloración del grafo completo de seis vértices habrá un triángulo monocromático; extrapolando se puede interpretar que de un grupo de seis personas siempre hay tres que se conocen mutuamente o tres que no se conocen mutuamente. La teoría de Ramsey estudia la generalización de esta idea para encontrar regularidad en el aparente desorden, e identificar condiciones generales para la existencia de subgrafos monocromáticos con alguna estructura dada.