Colorazione dei grafi

Una colorazione esatta dei vertici del grafo di Petersen con 3 colori, il numero minimo possibile.

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.

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, 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 Zykov (1949). Una delle principali applicazioni della colorazione dei grafi, l'allocazione dei registri nei compilatori, fu introdotta nel 1981.

Definizione e terminologia

Questo grafo può essere 3-colorato in 12 modi diversi.

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)²(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

$\chi (G)=\min\{k\,\colon \,P(G,k)>0\}.$

Polinomi cromatici per certi grafi

Triangolo K3	$t(t-1)(t-2)$
Grafo completo Kn	$t(t-1)(t-2)\cdots (t-(n-1))$
Albero con n vertici	$t(t-1)^{n-1}$
Ciclo Cn	$(t-1)^{n}+(-1)^{n}(t-1)$
Grafo di Petersen	$t(t-1)(t-2)(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t-352)$

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 è l'indice 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ì

$1\leq \chi (G)\leq n.\,$

I soli grafi che possono essere 1-colorati sono i grafi privi di ponti. Un grafo completo $K_{n}$ di n vertici richiede $\chi (K_{n})=n$ colori. In colorazione ottimale ci deve essere almeno uno degli m spigoli del grafo tra ogni coppia di classi di colore, così

$\chi (G)(\chi (G)-1)\leq 2m.\,$

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:

$\chi (G)\geq \omega (G).\,$

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,

$\chi (G)\leq \Delta (G)+1.\,$

I grafi completi hanno $\chi (G)=n$ e $\Delta (G)=n-1$, e i cicli dispari hanno $\chi (G)=3$ e $\Delta (G)=2$, 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: $\chi (G)\leq \Delta (G)$ 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 (Zykov (1949), Mycielski (1955)): 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 $L(G)$, e viceversa. Così,

$\chi '(G)=\chi (L(G)).\,$

C'è una relazione forte tra la colorabilità degli spigoli e il grado massimo del grafo $\Delta (G)$. Poiché tutti gli spigoli incidenti sullo stesso vertice hanno bisogno del proprio colore, abbiamo

$\chi '(G)\geq \Delta (G).\,$

Inoltre,

Teorema di König: $\chi '(G)=\Delta (G)$ se G è bipartito.

In generale, la relazione è ancora più forte di quella che il teorema di Brooks dà per la colorazione dei vertici:

Teorema di Vizing: un grafo di grado massimale $\Delta$ ha numero cromatico degli spigoli $\Delta$ o $\Delta +1$.

Altre proprietà

Un grafo ha una k-colorazione se e solo se ha un'orientazione aciclica per la quale il cammino più lungo ha al massimo lunghezza k; questo è il teorema di Gallai-Hasse-Roy-Vitaver (Nešetřil & Ossona de Mendez (2012)).

Per i grafi planari, le colorazioni dei vertici sono essenzialmente duali per i flussi zero in nessun luogo.

Sui grafi infiniti, si sa molto meno. Ecco due dei pochi risultati sulla colorazione dei grafi infiniti:

• Se tutti i sottografi finiti di un grafo infinito G sono k-colorabili, allora lo è anche G, in base all'assunzione dell'assioma della scelta. Si tratta del teorema di de Bruijn–Erdős (de Bruijn & Erdős (1951)).
• Se un grafo ammette una n-colorazione piena per ogni n ≥ n₀, esso ammette una colorazione piena infinita (Fawcett (1978).

Problemi aperti

Il numero cromatico del piano, dove due punti sono adiacenti se hanno distanza unitaria, è ignoto, sebbene sia uno tra 4, 5, 6 o 7. Altri problemi aperti concernenti il numero cromatico dei grafi includono la congettura di Hadwiger che afferma che ogni grafo con numero cromatico k ha un grafo completo su k vertici come minore, la congettura di Erdős–Faber–Lovász che limita il numero cromatico delle unioni dei grafi completi che hanno esattamente un vertice in comune per ogni coppia, e la congettura di Albertson secondo la quale tra i grafi k-cromatici i grafi completi sono quelli con il più piccolo numero di incroci.

Quando Birkhoff e Lewis introdussero il polinomio cromatico nel loro attacco al teorema dei quattro colori, essi congetturarono che per i grafi planari G, il polinomio $P(G,t)$ non ha zeri nella regione $[4,\infty )$. Anche se è noto che tale polinomio cromatico non ha zeri nella regione $[5,\infty )$ e che $P(G,4)\neq 0$, la loro congettura è ancora irrisolta. Rimane anche un problema irrisolto per caratterizzare i grafi che hanno lo stesso polinomio cromatico e per determinare quali polinomi sono cromatici.

Algoritmi

Colorazione dei grafi
Decisione
Nome	Colorazione dei grafi, k-colorazione
Entrata	Grafo G con n vertici. k intero
Uscita	G ammette una colorazione dei vertici esatta con k colori?
Tempo di esecuzione	O(2 nn)
Complessità	NP-completo
Riduzione da	3-soddisfacibilità
Garey–Johnson	GT4
Ottimizzazione
Nome	Numero cromatico
Entrata	Grafo G con n vertici
Uscita	χ(G)
Complessità	NP-difficile
Approssimabilità	O(n (log n)−3(log log n)2)
Inapprossimabilità	O(n1−ε) a meno che P = NP
Problema di conteggio
Nome	Polinomio cromatico
Entrata	Grafo G con n vertici. k intero
Uscita	Il numero P (G,k) di k-colorazioni esatte di G
Tempo di esecuzione	O(2 nn)
Complessità	#P-completo
Approssimabilità	FPRAS per casi ristretti
Inapprossimabilità	Nessun PTAS a meno che P = NP

Tempo polinomiale

Determinare se un grafo può essere colorato con 2 colori è equivalente a determinare se il grafo è o no bipartito, e perciò computabile in tempo lineare usando la ricerca in ampiezza. Più generalmente, il numero cromatico e una colorazione corrispondente di grafi perfetti possono essere computati in tempo polinomiale usando la programmazione semidefinita. Le formule chiuse per il polinomio cromatico sono note per molte classi di grafi, come la foresta, i grafi cordali, i cicli, le ruote e le scale, così questi possono essere stimati in tempo polinomiale.

Se il grafo è planare e ha un'ampiezza dei rami limitata (o è non planare ma ha un scomposizione conosciuta dei rami), allora può essere risolta in tempo polinomiale usando la programmazione dinamica. In generale, il tempo richiesto è polinomiale nella dimensione dei grafi, ma esponenziale nell'ampiezza dei rami.

Algoritmi esatti

Il metodo forza bruta per una k-colorazione considera ognuna delle $k^{n}$ assegnazioni di k colori a n vertici e controlla per ciascuna se è corretta. Per computare il numero cromatico e il polinomio cromatico, questa procedura si usa per ogni $k=1,\ldots ,n-1$, poco pratica per tutti tranne i più piccoli grafi in entrata.

Usando la programmazione dinamica e un limite al numero di insiemi indipendenti massimali, la k-colorabilità può essere deciso nel tempo e nello spazio $O(2,445^{n})$. Usando il principio di inclusione-esclusione e l'algoritmo di Yates per la trasformata zeta veloce, la k-colorabilità può essere decisa nel tempo $O(2^{n}n)$ per qualsiasi k. Gli algoritmi più veloci sono noti per la 3- e la 4-colorabilità, che può essere decisa nel tempo $O(1,3289^{n})$ e $O(1,7272^{n})$, rispettivamente.

Contrazione

La contrazione $G/uv$ del grafo G è il grafo ottenuto identificando i vertici u e v, rimuovendo qualsiasi spigolo tra di essi e sostituendoli con un singolo vertice w dove qualsiasi spigolo che era incidente su u o v è ridiretto a w. Questa operazione svolge un ruolo importante nell'analisi della colorazione dei grafi.

Il numero cromatico soddisfa la relazione di ricorrenza:

$\chi (G)={\text{min}}\{\chi (G+uv),\chi (G/uv)\}$

dovuta a Zykov (1949), dove u e v sono vertici non adiacenti, $G+uv$ è il grafo $uv$ aggiunto. Parecchi algoritmi sono basati sulla stima di questa ricorrenza, l'albero risultante dalla computazione è chiamato talvolta albero di Zykov. Il tempo di esecuzione si basa sull'euristica per la scelta dei vertici u e v.

Il polinomio cromatico soddisfa la seguente relazione di ricorrenza

$P(G-uv,k)=P(G/uv,k)+P(G,k)$

dove u e v vertici adiacenti e $G-uv$ è il grafo con lo spigolo $uv$ rimosso. $P(G-uv,k)$ rappresenta il numero di possibili colorazioni esatte del grafo, quando i vertici possono avere colori uguali o diversi. Il numero di colorazioni esatte viene perciò dalla somma di due grafi. Se i vertici u e v hanno colori diversi, allora possiamo anche considerare un grado, dove u e v sono adiacenti. Se u e v hanno gli stessi colori, possiamo altresì considerare un grafo, dove u e v sono contratti. La curiosità di Tutte su quali altre proprietà dei grafi soddisfacessero questa ricorrenza lo portò a scoprire una generalizzazione bivariata del polinomio cromatico, il polinomio di Tutte.

Le espressioni danno origine a una procedura ricorsiva, chiamata algoritmo di cancellazione-contrazione, che forma la base di molti algoritmi per la colorazione dei grafi. Il tempo di esecuzione soddisfa la stessa relazione di ricorrenza della successione di Fibonacci, così, nel caso peggiore, l'algoritmo si svolge nel tempo entro un fattore polinomiale di $((1+{\sqrt {5}})/2)^{n+m}=O(1,6180^{n+m})$ per n vertici ed m spigoli. L'analisi può essere migliorata entro un fattore polinomiale del numero $t(G)$ degli alberi ricoprenti del grafo in entrata. In pratica, si impiegano le strategie branch and bound e la reiezione dell'isomorfismo dei grafi per evitare alcune chiamate ricorsive, e il tempo di esecuzione dipende dall'euristica usata per cogliere la coppia di vertici.

Colorazione greedy

Due colorazioni greedy dello stesso grafo che usano ordini diversi dei vertici. L'esempio di destra generalizza ai grafi 2-colorabili con n vertici, dove l'algoritmo greedy spende $n/2$ colori.

L'algoritmo greedy considera i vertici in un ordine specifico $v_{1}$, ...,$v_{n}$ e assegna a $v_{i}$ il più piccolo colore disponibile non utilizzato dai vicini di $v_{i}$ tra $v_{1}$, ...,$v_{i-1}$, aggiungendo un colore nuovo se necessario. La qualità della colorazione risultante dipende dall'ordinamento prescelto. Esiste un ordinamento che conduce a una colorazione greedy (in inglese greedy coloring) con il numero ottimale di $\chi (G)$ colori. D'altro canto, le colorazioni greedy possono essere arbitrariamente sbagliate; ad esempio, il grafo a corona su n vertici può essere 2-colorato, ma ha un ordinamento che conduce a una colorazione greedy con $n/2$ colori.

Se i vertici $v_{i}$ sono ordinati secondo il loro grado $d(v_{i})$, la colorazione greedy risultante usa al massimo ${\displaystyle \max _{i}}({\text{min}}\{d(v_{i})+1,i\})$ colori, al massimo uno in più del grado massimo del grafo. Questa euristica è chiamata talvolta algoritmo di Welsh–Powell. Un'altra euristica dovuta a Brélaz stabilisce l'ordinamento dinamicamente mentre procede l'algoritmo, scegliendo poi il vertice adiacente al maggior numero di colori diversi. Molte altre euristiche per la colorazione dei grafi sono basate similmente sulla colorazione greedy per una specifica strategia statica o dinamica di ordinamento dei vertici; questi algoritmi sono chiamati talvolta algoritmi di colorazione sequenziale.

Algoritmi paralleli e distribuiti

Nel campo degli algoritmi distribuiti, la colorazione dei grafi è strettamente legata al problema della rottura della simmetria. Gli attuali algoritmi randomizzati all'avanguardia sono più veloci degli algoritmi deterministici per un grado massimo Δ sufficientemente grande. Gli algoritmi randomizzati più veloci impiegano la tecnica multiprove di Schneider et al.

In un grafo simmetrico, un algoritmo deterministico distribuito non può trovare una colorazione esatta dei vertici. Sono necessarie alcune informazioni al fine di rompere la simmetria. Un'assunzione tipica è che inizialmente ogni nodo abbia un identificatore unico, per esempio, dall'insieme {1, 2, ..., n}. Posto in altri termini, assumiamo che ci sia data una n-colorazione. La sfida è di ridurre il numero dei colori da n a, per es., Δ + 1. Più colori si impiegano, per es. O(Δ) invece di Δ + 1, meno sessioni di comunicazioni sono richieste.

Una versione diretta distribuita della versione dell'algoritmo greedy per (Δ + 1)-colorazione richiede Θ(n) sessioni di comunicazione nel caso peggiore − le informazioni possono essere propagate da una parte della rete a un'altra.

Il caso interessante più semplice è un n-ciclo. Richard Cole e Uzi Vishkin mostrano che c'è un algoritmo distribuito che riduce il numero dei colori da n a O(log n) in un unico passo di comunicazione sincrono. Iterando la stessa procedura, è possibile ottenere una 3-colorazione di un n-ciclo in O(log* n) passi di comunicazione (assumendo che abbiamo identificatori unici dei nodi).

La funzione log*, logaritmo iterato, è una funzione crescente in modo estremamente lento, "quasi costante". Quindi il risultato di Cole e Vishkin sollevava la questione se c'è un algoritmo distribuito in tempo costante per 3-colorare un n-ciclo. Linial (1992) mostrò che questo non è possibile: qualsiasi algoritmo deterministico distribuito richiede Ω(log* n) passi di comunicazione per ridurre una n-colorazione a una 3-colorazione in un n-ciclo.

La tecnica di Cole e Vishkin può essere applicata anche a grafi con grado limitato arbitrario; il tempo di esecuzione running time is poli(Δ) + O(log* n). La tecnica fu estesa ai grafi con dischi unitari di Schneider et al. Gli algoritmi deterministici più veloci per la (Δ + 1)-colorazione di un piccolo Δ sono dovuti a Leonid Barenboim, Michael Elkin e Fabian Kuhn. L'algoritmo di Barenboim et al. si svolge nel tempo O(Δ) + log*(n)/2, che è ottimale in termini di n poiché il fattore costante 1/2 non può essere migliorato a causa del limite inferiore di Linial. Panconesi et al. usano le somposizioni a rete per computare una Δ+1 colorazione nel tempo $2^{O({\sqrt {\log n}})}$.

Anche il problema della colorazione degli spigoli è stato studiato nel modello distribuito. Panconesi & Rizzi (2001) ottengono in questo modello una (2Δ − 1)-colorazione nel tempo O(Δ + log* n). Il limite inferiore per la colorazione distribuita dei vertici dovuta a Linial (1992) si applica anche al problema della colorazione distribuita degli spigoli.

Algoritmi decentralizzati

Gli algoritmi decentralizzati sono quelli dove non è permesso alcun passaggio di messaggi (in contrasto con gli algoritmi distribuiti in cui il passaggio locale di messaggi ha luogo), ed esistono algoritmi decentralizzati efficienti che coloreranno un grafo se esiste una colorazione esatta. Tali algoritmi assumono che un vertice sia in grado di percepire se uno qualsiasi dei suoi vicini stia usando lo stesso colore del vertice, cioè se esista un conflitto locale. Questa è un'assunzione lieve in altre applicazioni, ad es. nell'allocazione di canali senza fili è solitamente ragionevole assumere che una stazione sarà in grado di rivelare se altre trasmittenti interferenti stiano usando lo stesso canale (ad es. misurando l'SINR). Questa informazione di percezione è sufficiente per permettere agli algoritmi basati sugli automatismi di apprendimento di trovare una colorazione esatta dei grafi con probabilità uno, ad es. vedi Leith (2006) e Duffy (2008).

Complessità computazionale

La colorazione dei grafi è computazionalmente difficile (hard, in inglese). È NP-completo decidere se un dato grafo ammette una k-colorazione per un dato k eccetto per i casi k = 1 e k = 2. In particolare, è NP-difficile computare il numero cromatico. Il problema della 3-colorazione rimane NP-completa anche sui grafi planari di grado 4.

L'algoritmo di approssimazione più noto computa una colorazione di dimensione almeno entro un fattore O(n(log n)⁻³(log log n)²) del numero cromatico. Per tutti gli ε > 0, approssimare il numero n^1−ε è NP-difficile.

È anche NP-difficile colorare un grafo 3-colorabile con 4 colori e un grafo k-colorabile con k^{(log k) / 25} colori per una costante k sufficientemente grande.

Computare i coefficienti del polinomio cromatico è #P-difficile. Infatti, anche computare il valore di $\chi (G,k)$ è #P-difficile in un qualsiasi punto razionale k eccetto per k = 1 e k = 2. Non c'è nessun FPRAS (schema di approssimazione in tempo pienamente polinomiale) per stimare il polinomio cromatico in un qualsiasi punto razionale k ≥ 1,5 eccetto per k = 2 a meno che NP = RP.

Per la colorazione degli spigoli, il risultato della dimostrazione di Vizing dà un algoritmo che usa al massimo Δ+1 colori. Tuttavia, decidere tra i due valori candidati per il numero cromatico degli spigoli è NP-completo. In termini di algoritmi di approssimazione, l'algoritmo di Vizing mostra che il numero cromatico degli spigoli può essere approssimato entro 4/3, e il risultato della difficoltà mostra che non esiste nessun algoritmo (4/3 − ε ) per un qualsiasi ε > 0 a meno che P = NP. Questi sono tra i più vecchi risultati nella letteratura degli algoritmi di approssimazione, anche se nessuno dei due studi fa uso esplicito di quella nozione.

Applicazioni

Schedulazione

La colorazione dei vertici fa da modello a numerosi problemi di schedulazione. Nella forma più pura, occorre assegnare un dato insieme di compiti a spazi temporali (time slots), ogni compito richiede uno di tali spazi. I compiti possono essere schedulati in qualsiasi ordine, ma alcune coppie di compiti possono essere in conflitto, nel senso che non è possibile assegnarli allo stesso spazio temporale, ad esempio perché entrambi fanno affidamento su una risorsa condivisa. Il grafo corrispondente contiene un vertice per ogni compito e uno spigolo per ogni coppia di compiti confliggenti. Il numero cromatico del grafo è esattamente il "tempo di completamento" (o makespan) minimo, ossia il tempo ottimale per finire tutti i compiti senza conflitti.

I dettagli del problema di scheduliazione definiscono la struttura del grafo. Per esempio, quando si assegnano gli aeromobili ai voli, il grafo dei conflitti risultante è un grafo d'intervallo, così il problema della colorazione può essere risolto in modo efficiente. Nell'allocazione delle ampiezze di banda alle stazioni radio, il grafo dei conflitti risultante è un grafo delle unità disco, perciò il problema della colorazione è 3-approssimabile.

Allocazione dei registri

Un compilatore è un programma informatico che traduce un linguaggio di programmazione in un altro. Per migliorare il tempo di esecuzione del codice risultante, una delle tecniche di ottimizzazione dei compilatori è l'allocazione dei registri, dove i valori più frequentemente usati del programma compilato sono conservati nel registri del processore veloce. Idealmente, i valori sono assegnati ai registri in modo che possano tutti risiedere nei registri quando sono usati.

L'approccio dei libri di testo a questo problema è di modellarlo come un problema di colorazione dei grafi. Il compilatore costruisce un grafo d'interferenza, dove i vertici sono le variabili e uno spigolo connette due vertici se essi sono richiesti nello stesso momento. Se il grafo può essere colorato con k colori, allora qualsiasi insieme di variabili richieste nello stesso momento può essere immagazzinato al massimo in k registri.

Altre applicazioni

Il problema della colorazione dei grafi ha trovato numerose applicazioni, compreso l'abbinamento dei motivi.

Il gioco ricreativo sudoku può essere visto come il completamento di una 9-colorazione su un dato grafo specifico con 81 vertici.

Altre colorazioni

Teoria di Ramsey

Un'importante classe di problemi di colorazione impropri è studiata nella teoria di Ramsey, dove gli spigoli del grafo sono assegnati ai colori, e non c'è nessuna restrizione sui colori degli spigoli incidenti. Un esempio semplice è il teorema dell'amicizia, che afferma che in qualsiasi colorazione degli spigoli di $K_{6}$ il grafo completo di sei vertici ci sarà un triangolo monocromatico; spesso illustrato dicendo che qualsiasi gruppo di sei persone o ha tre estranei reciproci o tre conoscenti reciproci. La teoria di Ramsey si occupa delle generalizzazioni di questa idea per cercare la regolarità nel disordine, trovando le condizioni generali per l'esistenza di sottografi monocromatici con una data struttura.

Altre colorazioni

Colorazione per lista

Ciascun vertice sceglie da una lista di colori

Colorazione degli spigoli per lista

Ciascuno spigolo sceglie da una lista di colori

Colorazione totale

Sono colorati i vertici e gli spigoli

Colorazione armoniosa

Ogni coppia di colori appare su almeno un vertice

Colorazione totale

Ogni coppia di colori appare su almeno uno spigolo

Colorazione esatta

Ogni coppia di colori appare su esattamente uno spigolo

Colorazione aciclica

Ogni sottografo 2-cromatico è aciclico

Colorazione a stella

Ogni sottografo 2-cromatico è una collezione disgiunta di stelle

Colorazione forte

Ogni colore appare in ogni partizione di uguale dimensione esattamente una volta

Colorazione forte degli spigoli

Gli spigoli sono colorati in modo che ciascuna classe di colore induce un accoppiamento (equivalente a colorare il quadrato del grafo lineare)

Colorazione equilibrata

Le dimensioni delle classi di colore differiscono almeno di uno

T-colorazione

La distanza tra due colori di vertici adiacenti non deve appartenere all'insieme fisso T

Colorazione per rango

Se due vertici hanno lo stesso colore i, allora ogni cammino fra di essi contiene un vertice con colore maggiore di i

Colorazione degli spigoli a intervalli

Un colore di spigoli che si incontrano in un vertice comune deve essere contiguo

Colorazione circolare

Motivata dai sistemi di compiti nei quali la produzione produce in modo ciclico

Colorazione dei cammini

Modella un problema ricorrente nei grafi

Colorazione frazionata

I vertici possono avere molteplici colori, e su ciascuno spigolo la somma delle parti dei colori di ciascun vertice non è maggiore di uno

Colorazione orientata

Prende in considerazione l'orientazione degli spigoli del grafo

Cocolorazione

Una colorazione impropria dei vertici dove ogni classe di colore induce un insieme indipendente o una cricca

Sottocolorazione

Una colorazione impropria dei vertici dove ogni classe di colore induce un'unione di cricche

Colorazione difettosa

Una colorazione impropria dei vertici dove ogni classe di colore induce un sottografo di grado vincolato

Colorazione debole

Una colorazione impropria dei vertici dove ogni nodo non isolato ha almeno un vicino con un colore diverso

Colorazione per somma

Il criterio di minimalizzazione è la somma dei colori

Colorazione totale con distinzione dei vertici adiacenti

Una colorazione totale con la restrizione aggiuntiva che qualsiasi due vertici adiacenti hanno insiemi di colori diversi

Colorazione centrata

Ogni sottografo indotto connesso ha un colore che si è usato esattamente una volta

La colorazione può essere considerata anche per i grafi con segni con i grafi di guadagno.

Bibliografia

• L. Barenboim e M. Elkin, Distributed (Δ + 1)-coloring in linear (in Δ) time, in Proceedings of the 41st Symposium on Theory of Computing, 2009, pp. 111–120, DOI:10.1145/1536414.1536432, ISBN 978-1-60558-506-2.
• A. Panconesi e A. Srinivasan, On the complexity of distributed network decomposition, in Journal of Algorithms, vol. 20, 1996.
• J. Schneider, A new technique for distributed symmetry breaking (PDF), in Proceedings of the Symposium on Principles of Distributed Computing, 2010 (archiviato dall'url originale il 30 luglio 2013).
• J. Schneider, A log-star distributed maximal independent set algorithm for growth-bounded graphs (PDF), in Proceedings of the Symposium on Principles of Distributed Computing, 2008 (archiviato dall'url originale il 30 luglio 2013).
• R. Beigel e D. Eppstein, 3-coloring in time O(1.3289ⁿ), in Journal of Algorithms, vol. 54, 2), 2005, pp. 168–204, DOI:10.1016/j.jalgor.2004.06.008.
• A. Björklund, T. Husfeldt e M. Koivisto, Set partitioning via inclusion–exclusion, in SIAM Journal on Computing, vol. 39, n. 2009, pp. 546–563, DOI:10.1137/070683933.
• D. Brélaz, New methods to color the vertices of a graph, in Communications of the ACM, vol. 22, n. 4, 1979, pp. 251–256, DOI:10.1145/359094.359101.
• R. L. Brooks e W. T. Tutte, On colouring the nodes of a network, in Proceedings of the Cambridge Philosophical Society, vol. 37, n. 2, 1941, pp. 194–197, DOI:10.1017/S030500410002168X.
• N. G. de Bruijn e P. Erdős, A colour problem for infinite graphs and a problem in the theory of relations (PDF), in Nederl. Akad. Wetensch. Proc. Ser. A, vol. 54, 1951, pp. 371–373. URL consultato il 15 febbraio 2014 (archiviato dall'url originale il 10 marzo 2016). (= Indag. Math. 13)
• J.M. Byskov, Enumerating maximal independent sets with applications to graph colouring, in Operations Research Letters, vol. 32, n. 6, 2004, pp. 547–556, DOI:10.1016/j.orl.2004.03.002.
• G. J. Chaitin, Register allocation & spilling via graph colouring, in Proc. 1982 SIGPLAN Symposium on Compiler Construction, 1982, pp. 98–105, DOI:10.1145/800230.806984, ISBN 0-89791-074-5.
• R. Cole e U. Vishkin, Deterministic coin tossing with applications to optimal parallel list ranking, in Information and Control, vol. 70, n. 1, 1986, pp. 32–53, DOI:10.1016/S0019-9958(86)80023-7.
• T. H. Cormen, C. E. Leiserson e R. L. Rivest, Introduction to Algorithms, 1ª ed., The MIT Press, 1990.
• D. P. Dailey, Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete, in Discrete Mathematics, vol. 30, n. 3, 1980, pp. 289–293, DOI:10.1016/0012-365X(80)90236-8.
• K. Duffy, N. O'Connell e A. Sapozhnikov, Complexity analysis of a decentralised graph colouring algorithm (PDF), in Information Processing Letters, vol. 107, n. 2, 2008, pp. 60–63, DOI:10.1016/j.ipl.2008.01.002.
• B. W. Fawcett, On infinite full colourings of graphs, in Can. J. Math., XXX, 1978, pp. 455–457.
• F.V. Fomin, S. Gaspers e S. Saurabh, Improved Exact Algorithms for Counting 3- and 4-Colorings, in Proc. 13th Annual International Conference, COCOON 2007, Lecture Notes in Computer Science, vol. 4598, Springer, 2007, pp. 65–74, DOI:10.1007/978-3-540-73545-8_9, ISBN 978-3-540-73544-1.
• M. R. Garey e D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, 1979, ISBN 0-7167-1045-5.
• M. R. Garey, D. S. Johnson e L. Stockmeyer, Some simplified NP-complete problems, in Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, 1974, pp. 47–63, DOI:10.1145/800119.803884.
• L. A. Goldberg e M. Jerrum, Inapproximability of the Tutte polynomial, in Information and Computation, vol. 206, n. 7, luglio 2008, pp. 908–929, DOI:10.1016/j.ic.2008.04.003.
• A. V. Goldberg, S. A. Plotkin e G. E. Shannon, Parallel symmetry-breaking in sparse graphs, in SIAM Journal on Discrete Mathematics, vol. 1, n. 4, 1988, pp. 434–446, DOI:10.1137/0401044.
• V. Guruswami e S. Khanna, On the hardness of 4-coloring a 3-colorable graph, in Proceedings of the 15th Annual IEEE Conference on Computational Complexity, 2000, pp. 188–197, DOI:10.1109/CCC.2000.856749, ISBN 0-7695-0674-7.
• M. M. Halldórsson, A still better performance guarantee for approximate graph coloring, in Information Processing Letters, vol. 45, 1993, pp. 19–23, DOI:10.1016/0020-0190(93)90246-6.
• I. Holyer, The NP-completeness of edge-coloring, in SIAM Journal on Computing, vol. 10, n. 4, 1981, pp. 718–720, DOI:10.1137/0210055.
• P. Crescenzi e V. Kann, How to find the best approximation results — a follow-up to Garey and Johnson, in ACM SIGACT News, vol. 29, n. 4, dicembre 1998, p. 90, DOI:10.1145/306198.306210.
• F. Jaeger, D. L. Vertigan e D. J. A. Welsh, On the computational complexity of the Jones and Tutte polynomials, in Mathematical Proceedings of the Cambridge Philosophical Society, vol. 108, 1990, pp. 35–53, DOI:10.1017/S0305004100068936.
• T. R. Jensen e B. Toft, Graph Coloring Problems, Wiley-Interscience, New York, 1995, ISBN 0-471-02865-7.
• S. Khot, Improved inapproximability results for MaxClique, chromatic number and approximate graph coloring, in Proc. 42nd Annual Symposium on Foundations of Computer Science, 2001, pp. 600–609, DOI:10.1109/SFCS.2001.959936, ISBN 0-7695-1116-3.
• M. Kubale, Graph Colorings, American Mathematical Society, 2004, ISBN 0-8218-3458-4.
• F. Kuhn, Weak graph colorings: distributed algorithms and applications, in Proceedings of the 21st Symposium on Parallelism in Algorithms and Architectures, 2009, pp. 138–144, DOI:10.1145/1583991.1584032, ISBN 978-1-60558-606-9.
• E.L. Lawler, A note on the complexity of the chromatic number problem, in Information Processing Letters, vol. 5, n. 3, 1976, pp. 66–67, DOI:10.1016/0020-0190(76)90065-X.
• D.J. Leith e P. Clifford, A Self-Managed Distributed Channel Selection Algorithm for WLAN (PDF), in Proc. RAWNET 2006, Boston, MA, 2006.
• N. Linial, Locality in distributed graph algorithms, in SIAM Journal on Computing, vol. 21, n. 1, 1992, pp. 193–201, DOI:10.1137/0221015.
• J. H. van Lint e R. M. Wilson, A Course in Combinatorics, 2ª ed., Cambridge University Press, 2001, ISBN 0-521-80340-3.
• Dániel Marx, Graph colouring problems and their applications in scheduling, in Periodica Polytechnica, Electrical Engineering, vol. 48, 1–2, 2004, pp. 11–16, CiteSeerX: 10.1.1.95.4268.
• J. Mycielski, Sur le coloriage des graphes (PDF), in Colloq. Math., vol. 3, 1955, pp. 161–162.
• Jaroslav Nešetřil e Patrice Ossona de Mendez, Theorem 3.13, in Sparsity: Graphs, Structures, and Algorithms, Algorithms and Combinatorics, vol. 28, Heidelberg, Springer, 2012, p. 42, DOI:10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, MR 2920058.
• Alessandro Panconesi e Romeo Rizzi, Some simple distributed algorithms for sparse networks, in Distributed Computing, vol. 14, n. 2, Berlino, New York, Springer-Verlag, 2001, pp. 97–100, DOI:10.1007/PL00008932, ISSN 0178-2770.
• K. Sekine, H. Imai e S. Tani, Computing the Tutte polynomial of a graph of moderate size, in Proc. 6th International Symposium on Algorithms and Computation (ISAAC 1995), Lecture Notes in Computer Science, vol. 1004, Springer, 1995, pp. 224–233, DOI:10.1007/BFb0015427, ISBN 3-540-60573-8.
• D. J. A. Welsh e M. B. Powell, An upper bound for the chromatic number of a graph and its application to timetabling problems, in The Computer Journal, vol. 10, n. 1, 1967, pp. 85–86, DOI:10.1093/comjnl/10.1.85.
• D. B. West, Introduction to Graph Theory, Prentice-Hall, 1996, ISBN 0-13-227828-6.
• H. S. Wilf, Algorithms and Complexity, Prentice–Hall, 1986.
• D. Zuckerman, Linear degree extractors and the inapproximability of Max Clique and Chromatic Number, in Theory of Computing, vol. 3, 2007, pp. 103–128, DOI:10.4086/toc.2007.v003a006.
• (RU) A. A. Zykov, О некоторых свойствах линейных комплексов (Su alcune proprietà dei complessi lineari), in Math. Sbornik., 24(66), n. 2, 1949, pp. 163–188.
• Tommy R. Jensen e Bjarne Toft, Graph Coloring Problems, John Wiley & Sons, 1995, ISBN 978-0-471-02865-9.

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file sulla colorazione dei grafi

Collegamenti esterni

• (EN) Eric W. Weisstein, Graph Coloring, su MathWorld, Wolfram Research.
• (EN) graph colouring, in Free On-line Dictionary of Computing, Denis Howe. Disponibile con licenza GFDL
• (EN) Graph Coloring Page by Joseph Culberson (graph coloring programs)
• (EN) CoLoRaTiOn by Jim Andrews and Mike Fellows is a graph coloring puzzle
• (EN) Links to Graph Coloring source codes, su adaptivebox.net. URL consultato il 15 febbraio 2014 (archiviato dall'url originale il 4 luglio 2008).
• (EN) Code for efficiently computing Tutte, Chromatic and Flow Polynomials Archiviato il 16 aprile 2008 in Internet Archive. by Gary Haggard, David J. Pearce and Gordon Royle
• (EN) Graph Coloring Web Application, su graph-coloring.appspot.com. URL consultato il 30 aprile 2019 (archiviato dall'url originale il 6 maggio 2019).

Controllo di autorità	LCCN (EN) sh2004000285 · J9U (EN, HE) 987007539706505171