La coloración de grafos es un conjunto de problemas de la teoría de grafos que consiste en asignar colores, símbolos o etiquetas a los elementos de un grafo siguiendo reglas concretas. La versión más conocida pide colorear los vértices de modo que dos vértices adyacentes no compartan color.
El objetivo suele ser usar la menor cantidad posible de colores. Ese mínimo recibe el nombre de número cromático y se representa a menudo con la letra griega chi. Encontrarlo no es sencillo en general: para muchos grafos, calcularlo exactamente es un problema difícil desde el punto de vista computacional.
Variantes principales
La coloración de vértices no es la única forma de este problema. También se estudian otras versiones que cambian el tipo de elemento a colorear o las restricciones impuestas por la estructura del grafo.
- Coloración de vértices: evita que dos vértices conectados tengan el mismo color.
- Coloración de aristas: exige que aristas incidentes en un mismo vértice tengan colores distintos.
- Coloración por listas: cada vértice dispone de un conjunto limitado de colores permitidos.
Origen e importancia
El interés por estos problemas creció a partir de cuestiones de cartografía, como el reparto de colores en mapas para distinguir regiones vecinas. Con el tiempo, la idea se extendió a la informática y a las matemáticas discretas. La relación entre mapas y colores ayudó a popularizar resultados como el teorema de los cuatro colores, que afirma que basta con cuatro colores para colorear cualquier mapa plano bajo ciertas condiciones.
Más allá de la geometría, la coloración es útil porque transforma restricciones de compatibilidad en una asignación concreta. Por eso aparece en problemas de planificación, donde dos tareas que se superponen no pueden recibir el mismo recurso.
Aplicaciones frecuentes
- Diseño de horarios para evitar coincidencias entre clases, exámenes o turnos.
- Asignación de frecuencias en redes inalámbricas para reducir interferencias.
- Compilación y gestión de recursos en informática, por ejemplo al asignar registros.
- Modelado de conflictos en redes sociales, laboratorios o transporte.
En la práctica, muchos algoritmos buscan buenas soluciones aunque no siempre garanticen la mínima posible. Por eso la coloración de grafos es un área activa de estudio: combina teoría, optimización y aplicaciones reales. Su valor está en ofrecer un lenguaje común para describir conflictos, limitaciones y recursos compartidos.
