Coloración de grafos

En representaciones matemáticas y computacionales se utilizan típicamente enteros no negativos como colores.

En 1890, Heawood descubrió que el argumento de Kempe contenía un error, en ese artículo probó el teorema de los 5 colores, diciendo que cada mapa plano puede ser coloreado con, a lo más 5 colores, sin embargo, seguía usando ideas de Kempe.

El menor número de colores necesario para colorear un grafo G se llama número cromático y se denota como χ(G).

Un grafo al 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.

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.

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.

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: 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.

Esto es, 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 Más aún, 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.