El número cromático de una gráfica $G$ es la menor cantidad de colores necesarios para colorear sus vértices sin que dos vertices vecinos (unidos por una arista) tengan el mismo color. O más formalmente, es el menor entero $m$ tal que G es $m$-coloreable (o bien, tiene una coloración propia con $m$ colores). A este número se le denota como $\chi(G)$, es decir, $\chi(G)=m$.
Es fácil ver que si coloreamos todos los vértices de colores distintos, entonces se satisfacerá que la gráfica tiene una coloración propia, es decir, sin que dos vértices unidos por una arista tengan el mismo color (ver figura 1.a). Pero evidentemente, esto generalmente no nos da el número cromático, pues puede ser posible colorear las gráficas con muchos menos colores, como en el ejemplo de la siguiente figura:
 |
 |
| Poniendo un color distinto en cada vértice produce una coloración propia, pero no es mínima. | Esta es una 3-coloración de la mísma gráfica. De hecho, el número cromático de esta gráfica es 3. |