Teoría de grafos · Definición

Coloración de grafos

matemáticas discretasgrafos

Antes de empezar necesitas conocer

Colorear un grafo es la forma abstracta de repartir recursos en conflicto: horarios de exámenes, frecuencias de radio o registros de un compilador.

Definición

Una coloración propia \(c\) con \(k\) colores de un grafo \(G=(V,E)\) asigna a cada vértice uno de los colores \(1,\dots,k\) sin que dos vértices adyacentes compartan color.

\[c:V\to\{1,\dots,k\},\qquad c(u)\neq c(v)\ \text{ si } \{u,v\}\in E\]

El número cromático \(\chi(G)\) es el menor \(k\) para el que existe una coloración propia. Se cumple \(\chi(G)=1\) solo si no hay aristas, y \(\chi(G)=2\) exactamente cuando \(G\) tiene aristas y es bipartito. En \(K_n\) todos los vértices son adyacentes, así que \(\chi(K_n)=n\); en un ciclo, \(\chi(C_n)=2\) si \(n\) es par y \(3\) si es impar.

Dos observaciones dan cotas. Si \(G\) contiene un subgrafo completo \(K_r\), entonces \(\chi(G)\ge r\), porque esos \(r\) vértices usan colores distintos. Y si \(\Delta\) es el grado máximo, un coloreo voraz (colorear los vértices uno a uno con un color libre) usa a lo más \(\Delta+1\) colores, pues cada vértice tiene a lo más \(\Delta\) vecinos ya coloreados. El teorema de Brooks afina esto: salvo los grafos completos y los ciclos impares, bastan \(\Delta\) colores.

Un ejemplo guía es la programación de exámenes: los cursos son vértices, hay una arista cuando comparten estudiantes y cada color es un horario; \(\chi(G)\) es el menor número de horarios sin choques. Un error frecuente es creer que el coloreo voraz siempre da el mínimo: depende del orden de los vértices, y encontrar \(\chi(G)\) es difícil en general. El célebre teorema de los cuatro colores afirma que todo grafo planar se colorea con 4 colores.

Para pensar

¿Por qué una coloración propia de un grafo con una arista nunca puede usar un solo color?

Los dos extremos de la arista son adyacentes y deben tener colores distintos, así que se necesitan al menos dos colores.

Un grafo tiene \(\chi(G)=3\). ¿Puede contener un \(K_4\)?

No. Un \(K_4\) obliga a \(\chi(G)\ge4\), lo que contradice \(\chi(G)=3\).

Ejercicios 10

  1. ¿Cuántos colores necesita como mínimo una coloración propia del grafo completo \(K_5\)?
  2. ¿Cuántos colores necesita como mínimo un grafo que tiene al menos una arista?
  3. ¿Cuántos colores necesita como mínimo el ciclo \(C_7\) (7 vértices)?
  4. ¿Cuántos colores necesita como mínimo el ciclo \(C_8\)?
  5. El grafo tiene vértices \(1,2,3,4\) y aristas \(\{1,2\},\{2,3\},\{1,3\},\{3,4\}\). ¿Cuál es una coloración propia?
  6. La rueda \(W_5\) es un ciclo \(C_5\) más un vértice central unido a los 5 vértices del ciclo. ¿Cuántos colores necesita?
  7. ¿De cuántas formas se puede colorear un camino de 4 vértices con 3 colores disponibles, de modo que vértices adyacentes difieran?
  8. El grafo de Petersen tiene 10 vértices, todos de grado 3, y contiene ciclos de longitud 5. ¿Cuál es el mínimo número de colores de una coloración propia?
  9. Sea \(\Delta\) el grado máximo de un grafo \(G\). ¿Qué afirmación es verdadera para todo grafo?
  10. Si un grafo \(G\) contiene a \(K_4\) como subgrafo, ¿qué se puede asegurar sobre el mínimo número de colores \(\chi(G)\)?

Referencias

  • Kenneth H. Rosen, Discrete Mathematics and Its Applications, 8th edition, McGraw-Hill, 2019. §10.8
  • Susanna S. Epp, Discrete Mathematics with Applications, 5th edition, Cengage, 2019. §10.8
  • Ralph P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction, 5th edition, Pearson, 2003. §11.6