Nella teoria dei grafi, la colorazione dei grafi è un caso speciale di etichettamento dei grafi; è un'assegnazione di etichette, tradizionalmente chiamate "colori", agli elementi di un grafo soggetta a determinati vincoli. Nella sua forma più semplice, è un modo di colorare i vertici di un grafo tale che nessuno dei due vertici adiacenti condivida lo stesso colore; questo prende il nome di colorazione dei vertici. Similmente, una colorazione degli spigoli assegna un colore a ogni spigolo in modo che nessuno dei due spigoli adiacenti condivida lo stesso colore, e una colorazione delle facce di un grafo planare assegna un colore a ogni faccia o regione in modo tale che nessuna delle due facce che condividono un confine abbia lo stesso colore.
La colorazione dei vertici è il punto di partenza dell'argomento, e gli altri problemi di colorazione possono essere trasformati in una versione dei vertici. Ad esempio, una colorazione degli spigoli di un grafo è solo una colorazione dei vertici del suo grafo di linea, e una colorazione delle facce di un grafo planare è solo una colorazione dei vertici del suo duale. Tuttavia, i problemi di colorazione dei vertici sono spesso dichiarati e studiati come sono. Questo è in parte per la prospettiva, e in parte perché alcuni problemi si studiano meglio in forma diversa dai vertici, com'è ad esempio la colorazione degli spigoli.
La convenzione di usare i colori trae origine dalla colorazione dei paesi di una mappa, dove ogni faccia è colorata in senso letterale. Questo fu poi generalizzato alla colorazione delle facce di un grafo incorporato nel piano. A causa della dualità planare si passò alla colorazione dei vertici, e in questa forma si generalizza a tutti i grafi. Nelle rappresentazioni matematiche e informatiche, è tipico usare i primi interi positivi o non negativi come "colori". In generale, si può usare qualsiasi insieme finito come "insieme dei colori". La natura del problema della colorazione dipende dal numero dei colori, ma non da quali sono.
La colorazione dei grafi gode di molte applicazioni pratiche come pure di molte sfide teoriche. Oltre ai problemi di tipo classico, si possono anche porre diverse limitazioni sul grafo, o sul modo in cui un colore è assegnato, o perfino sul colore stesso. L'argomento ha raggiunto popolarità anche presso il grande pubblico sotto la forma del popolare rompicapo sudoku. La colorazione dei grafi è ancora un campo di ricerca molto attivo.
Nota: molti termini usati in questo articolo sono definiti in Glossario di teoria dei grafi.
Storia
I primi risultati sulla colorazione dei grafi trattano quasi esclusivamente di grafi planari sotto la forma della colorazione delle mappe. Mentre tentava di colorare una mappa delle contee dell'Inghilterra, Francis Guthrie postulò il teorema dei quattro colori, notando che quattro colori erano sufficienti a colorare la mappa così che nessuna regione che condividesse una frontiera comune ricevesse lo stesso colore. Il fratello di Guthrie passò la questione al suo insegnante di matematica Augustus de Morgan allo University College, che la menzionò in una lettera a William Hamilton nel 1852. Arthur Cayley sollevò il problema a una riunione della London Mathematical Society nel 1879. Lo stesso anno, Alfred Kempe pubblicò un saggio che asseriva di aver stabilito il risultato, e per un decennio il problema dei quattro colori fu considerato risolto. Per la sua impresa, Kempe fu eletto membro della Royal Society e in seguito presidente della London Mathematical Society.M. Kubale, History of graph coloring, in
Nel 1890, Heawood mise in evidenza che l'argomentazione di Kempe era sbagliata. Tuttavia, in quel saggio dimostrò il teorema dei cinque colori, dicendo che ogni mappa planare può essere colorata con non più di cinque colori, usando idee di Kempe. Nel secolo seguente, fu sviluppata una vasta quantità di lavoro e di teorie per ridurre il numero dei colori a quattro, finché il teorema dei quattro colori non fu alla fine dimostrato nel 1976 da Kenneth Appel e Wolfgang Haken. La dimostrazione risaliva alle idee di Heawood e Kempe e ignorava in gran parte gli sviluppi intervenuti.. La dimostrazione del teorema dei quattro colori è notevole anche per essere la prima importante dimostrazione assistita dal computer.
Nel 1912, George David Birkhoff introdusse il polinomio cromatico per studiare i problemi della colorazione, che fu poi generalizzato da Tutte nel polinomio di Tutte, importante struttura nella teoria algebrica dei grafi. Kemoe aveva già attirato l'attenzione sul caso generale, non planare, nel 1879,, p. 2 e molti risultati sulle generalizzazioni della colorazione dei grafi planari a superfici di ordine superiore seguirono all'inizio del XX secolo.
Nel 1960, Claude Berge formulò un'altra congettura sulla colorazione dei grafi, la congettura forte del grafo perfetto, originariamente motivata da un concetto della teoria dell'informazione chiamato capacità di errore zero di un grafo, introdotto da Shannon. La congettura rimase irrisolta per 40 anni, finché nel 2002 fu enunciata come il celebre teorema forte del grafo perfetto da Chudnovsky, Robertson, Seymour e Thomas.
La colorazione dei grafi è studiata come problema algoritmico fin dai primi anni 1970: il problema del numero cromatico è uno dei 21 problemi NP-completi di Karp del 1972, e approssimativamente nello stesso periodo furono sviluppati vari algoritmi del tempo esponenziale basati sul percorso a ritroso (backtracking) e sulla ricorrenza contrazione-cancellazione di . Una delle principali applicazioni della colorazione dei grafi, l'allocazione dei registri nei compilatori, fu introdotta nel 1981.
Definizione e terminologia
Colorazione dei vertici
Quando è usata senza alcuna specificazione, la colorazione di un grafo è quasi sempre una colorazione esatta dei vertici, cioè un'etichettatura dei vertici del grafo con colori tali che nessuna coppia di vertici che condividono lo stesso spigolo abbiano lo stesso colore. Poiché un vertice con un cappio non potrebbe mai essere colorato esattamente, si comprende che i grafi in questo contesto sono senza cappio.
La terminologia di usare i colori per le etichette dei vertici risale alla colorazione delle mappe. Etichette come rosso e blu si usano soltanto quando il numero di colori è piccolo, e normalmente si intende che le etichette sono tratte dagli interi {1,2,3,...}.
Una colorazione che usa al massimo k colori è chiamata k-colorazione (esatta). Il numero minimo di colori richiesti per colorare un grafo G è chiamato il suo numero cromatico ed è spesso denotato χ(G). Talvolta si usa γ(G), dal momento che χ(G) si usa anche per la caratteristica di Eulero di un grafo. Un grafo a cui può essere assegnato una k-colorazione (esatta) è k-colorabile, ed è k-cromatico se il suo numero cromatico è esattamente k. Un sottoinsieme di vertici assegnati allo stesso colore è chiamato classe di colore, ogni classe di questo tipo forma un insieme indipendente. Così, una k-colorazione è la stessa di una partizione dell'insieme dei vertici in k insiemi indipendenti, e i termini k-partito e k-colorabile hanno lo stesso significativo.
Polinomio cromatico
Il polinomio cromatico conta il numero di modi in cui un grafo può essere colorato usando non più di un dato numero di colori. Ad esempio, usando tre colori, il grafo nell'immagine a destra può essere colorato l in 12 modi. Con soli due colori, non può essere affatto colorato. Con quattro colori, può essere colorato in 24 + 4⋅12 = 72 modi: usando tutti e quattro i colori, ci sono 4! = 24 colorazioni valide (ogni assegnazione di quattro colori a qualsiasi grafo su 4 vertici è una colorazione esatta); e per ogni scelta di tre dei quattro colori, ci sono 12 3-colorazioni valide. Così, per il grafo dell'esempio, una tabella del numero di colorazioni valide inizierebbe in questo modo: Colori disponibili 1 2 3 4 …Numero di colorazioni 0 0 12 72 …
Il polinomio cromatico è una funzione P(G, t) che conta il numero di t-colorazioni di G. Come indica il nome, per un dato G la funzione è in realtà un polinomio in t. Per il grafo dell'esempio, P(G, t) = t(t − 1)2(t − 2), e infatti P(G, 4) = 72.
Il polinomio cromatico include almeno altrettante informazioni sulla colorabilità di G del numero cromatico. Infatti, χ è il più piccolo intero positivo che non è una radice del polinomio cromatico
+Polinomi cromatici per certi grafi Triangolo K3 Grafo completo Kn Albero con n vertici Ciclo Cn Grafo di Petersen
Colorazione degli spigoli
Una colorazione degli spigoli di un grafo è una colorazione esatta degli spigoli, che significa un'assegnazione di colori agli spigoli così che nessun vertice sia incidente a due spigoli dello stesso colore. Una colorazione degli spigoli con k colori è chiamata una k-colorazione degli spigoli ed è equivalente al problema di ripartire l'insieme degli spigoli in k accoppiamenti. Il più piccolo numero di colori richiesto per una colorazione degli spigoli di un grafo G è lindice cromatico, o numero cromatico degli spigoli, χ′(G). Una colorazione di Tait è una 3-colorazione degli spigoli di un grafo cubico. Il teorema dei quattro colori è equivalente all'asserzione che ogni grafo cubico planare privo di ponti ammette una colorazione di Tait.
Colorazione totale
La colorazione totale è un tipo di colorazione sui vertici e sugli spigoli di un grafo. Quando si usa senza alcuna specificazione, si assume che una colorazione totale sia sempre esatta, nel senso che a nessun vertice adiacente, a nessuno spigolo adiacente e a nessuno spigolo e ai vertici estremi è assegnato lo stesso colore. Il numero cromatico totale χ″(G) di un grafo G è il numero minimo di colori richiesto in qualsiasi colorazione totale di G.
Proprietà
Limiti al numero cromatico Assegnare colori distinti a vertici distinti produce sempre una colorazione esatta, così
I soli grafi che possono essere 1-colorati sono i grafi privi di ponti. Un grafo completo di n vertici richiede colori. In colorazione ottimale ci deve essere almeno uno degli m spigoli del grafo tra ogni coppia di classi di colore, così
Se G contiene una cricca di dimensione k, allora sono necessari almeno k colori per colorare quella cricca; in altre parole, il numero cromatico è almeno il numero della cricca:
Per i grafi d'intervallo questo limite è stretto.
I grafi 2-colorabili sono esattamente i grafi bipartiti, che includono gli alberi e le foreste. Per il teorema dei quattro colori, ogni grafo planare può essere 4-colorato.
Una colorazione greedy mostra che ogni grafo può essere colorato con un colore in più del grado massimo dei vertici,
I grafi completi hanno e , e i cicli dispari hanno e , così per questi grafi questo limite è il migliore possibile. In tutti gli altri casi, il limite può essere leggermente migliorato; il teorema di Brooks. afferma che Teorema di Brooks: per un grafo connesso, semplice G, a meno che G non sia un grafo completo o un ciclo dispari.
Grafi con numero cromatico elevato I grafi con grandi cricche hanno numero cromatico elevato, ma non è vero il contrario. Il grafo di Grötzsch è un esempio di grafo 4-cromatico senza un triangolo, e l'esempio può essere generalizzato ai grafi di Mycielski. Teorema di Mycielski (, ): esistono grafi senza triangoli con numero cromatico arbitrariamente elevato.
Dal teorema di Brooks, i grafi con numero cromatico elevato devono avere il grado massimo elevato. Un'altra proprietà locale che porta a un numero cromatico elevato è la presenza di una grande cricca. Ma la colorabilità non un fenomeno interamente locale: un grafo con calibro elevato somiglia localmente a un albero, perché tutti i cicli sono lunghi, ma il suo numero cromatico non deve essere 2: Teorema (Erdős): esistono grafi di calibro e numero cromatico arbitrariamente elevati.
Limiti all'indice cromatico Una colorazione dei vertici di G è una colorazione dei vertici del suo grafo di linea , e viceversa. Così,