Explorador de coloreo de grafos

El número cromático χ(G) es la cantidad mínima de colores necesaria para que ninguna arista una a dos vértices del mismo color. Calcularlo exactamente es NP-difícil — la mejor garantía general se sitúa entre una cota inferior por clique (toda clique de tamaño k obliga a usar al menos k colores) y una cota superior voraz (el coloreo de Welsh-Powell, por grado descendente, nunca usa más de Δ+1 colores, donde Δ es el grado máximo). Para los grafos planares — los que se pueden dibujar sin que se crucen las aristas — el teorema de los cuatro colores garantiza que 4 colores siempre bastan; se demostró por primera vez con un ordenador en 1976 y sigue siendo uno de los pocos teoremas importantes que requieren una verificación exhaustiva de casos por computadora. El coloreo de grafos subyace a problemas reales de asignación: la asignación de registros en compiladores, la programación de exámenes y la asignación de frecuencias de radio se reducen todos a colorear un grafo de conflictos.

La coloración de grafos se reduce a una regla: ninguna arista puede unir dos vértices del mismo color, y quieres usar la menor cantidad de colores posible. Esa única condición lo decide todo. Una prueba útil: todo ciclo de longitud par se colorea con 2 colores, pero todo ciclo de longitud impar necesita 3 — así que un triángulo (el ciclo impar más pequeño) nunca puede colorearse con 2. Construye ambos en la herramienta y observa el número de conflictos.

Colorear los vértices uno a uno eligiendo siempre el color libre más bajo parece seguro, pero el orden importa muchísimo. En una familia llamada grafos corona — 2n vértices que solo necesitan 2 colores — un orden malicioso obliga al método voraz a usar n colores en su lugar. Su peor caso no tiene cota, y por eso el autocoloreado de la herramienta ordena los vértices por grado descendente (Welsh-Powell) para esquivar esas trampas.