Primi elementi della teoria dei grafi

Numeri cromatici

Il numero cromatico di un grafo è il numero minimo di colori necessari per colorare i vertici del grafo in modo che due vertici adiacenti non abbiano lo stesso colore. In tutti i grafi in cui i vertici sono allineati il numero cromatico è 2 (basta alternare i colori); questi grafi sono detti 2-colorabili. Un grafo ciclico C_n è 2-colorabile se n è pari ed è 3-colorabile se n è dispari.

Un grafo bipartito K_m,n è 2-colorabile mentre un grafo completo K_n è n-colorabile

Come possiamo stabilire il numero cromatico di un grafo? Se G è un grafo planare sappiamo, dal teorema dei quattro colori, che il suo numero cromatico è al massimo 4. Ma se G è un grafo non planare? Esiste una relazione tra il numero cromatico χ(G) e il grado massimo Δ(G) dei vertici di un grafo connesso semplice G scoperta dal matematico Brooks. Per i grafi completi e per i grafi ciclici con n dispari si ha:

χ(G) = Δ(G) + 1

Per tutti gli altri grafi vale la disuguaglianza;

χ(G) ≤ Δ(G)

Quest'ultima relazione non ci dice qual è il numero cromatico esatto ma pone una limitazione: il numero cromatico è minore o uguale al grado massimo dei vertici. Ad esempio, il grafo in figura è regolare di grado 3 e quindi il suo numero cromatico è al massimo 3.

Come si vede il grafo ha un ciclo C₅ e quindi non può avere un numero cromatico minore di 3.

Anche il seguente grafo è regolare di grado 3 e quindi il suo numero cromatico è al massimo 3.

Però il grafo presenta solo cicli C₄ e quindi il suo numero cromatico è 2.