grafo G se define como un par (V, A), donde V es un conjunto no vacío cuyos elementos son denominados vértices o nodos y A es un subconjunto de pares no ordenados de vértices que reciben el nombre de aristas o arcos.

Si V = {v₁, v₂, ...,v_n}, los elementos de A se representan de la forma {v_i, v_j} con i ≠ j . Dos vértices v_i y v_j se dicen adyacentes si {v_i, v_j} Î A.

La representación gráfica de un grafo se lleva a cabo asociando a cada vértice un punto del plano y a cada arista {v_i, v_j} una línea continua que une los puntos asociados a los vértices v_i y v_j. No existe ninguna restricción sobre la forma de las líneas que representan las aristas.

Una coloración propia de G ocurre cuando se asignan colores a los vértices de G de modo que si v_i y v_j  son adyacentes, entonces v_i y v_j tengan colores distintos asignados. El número mínimo de colores necesarios para una coloración propia de un grafo es lo que se conoce como número cromático del grafo.

Una forma fácil de determinar el número cromático de un grafo simple es analizando los autovalores asociados a su matriz de vecindades o matriz de adyacencia. Un grafo es simple si a lo sumo sólo una arista une dos vértices cualesquiera. Es decir, un grafo sin bucles ni aristas paralelas.

Si V = {v₁, v₂, ...,v_n} es el conjunto de vértices, el grafo se puede describir mediante una matriz n × n, cuyas filas y columnas se hallan etiquetadas con los vértices y cuyos coeficientes serán: uno si A o cero en caso contrario. Como se puede observar, la matriz de adyacencia depende de la ordenación de los vértices. No obstante, siempre será una matriz simétrica con diagonal principal nula.

A modo de ejemplo, se escribirá la matriz de adyacencia del grafo que se muestra en la siguiente figura.

La matriz de adyacencia del grafo mostrado es:

Como la matriz de adyacencia es simétrica, los autovalores asociados a la misma son siempre números reales. Por lo tanto, éstos pueden ser ordenados de mayor a menor.

Sea l₁ el autovalor más grande y l_n, el autovalor más pequeño. Si x es el número cromático de un grafo simple, entonces se cumple:

Se determinará el número cromático del grafo de la Figura 2. Para ello, se deberán calcular los autovalores asociados a la matriz de adyacencia de este grafo. Por ejemplo, se podría utilizar Scilab para obtenerlos, con el comando spec.

Los autovalores de la matriz son: -2,6095952,  -1,9749714, -1,4179733,  -1, -0,6173948, -0,3889106,  0,3905697, 1,2850306, 2,1951342, 4,138111.

Aplicando la desigualdad (2) se obtiene:

Por lo tanto, el número cromático del grafo es x = 4. Esto significa que cuatro es el número mínimo necesario de colores distintos para colorear el grafo de la Figura 2 de manera tal que no hayan dos vértices consecutivos con el mismo color. La coloración se muestra en la figura siguiente: