Visualizza wikitesto di Colorazione dei grafi

[[File:Petersen graph 3-coloring.svg|thumb|right|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 [[Grafo duale|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 [[Incorporazione dei grafi|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==
{{vedi anche | Teorema dei quattro colori | Teoria dei grafi}}

I primi risultati sulla colorazione dei grafi trattano quasi esclusivamente di [[Grafo planare|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 (Londra)|University College]], che la menzionò in una lettera a [[William Rowan Hamilton|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.<ref>M. Kubale, ''History of graph coloring'', in {{Cita|Kubale (2004)|}}</ref>

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.<ref>{{Cita|van Lint & Wilson (2001)|cap. 33}}.</ref> 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 [[William Thomas Tutte|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,<ref>{{Cita|Jensen & Toft (1995)||Jensen & Tof (1995)}}, p. 2</ref> 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 [[Claude Shannon|Shannon]]. La congettura rimase irrisolta per 40 anni, finché nel 2002 fu enunciata come il celebre [[teorema forte del grafo perfetto]] da [[Maria Chudnovsky|Chudnovsky]], [[Neil Robertson (matematico)|Robertson]], [[Paul Seymour (matematico)|Seymour]] e [[Robin Thomas (matematico)|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 {{Cita|Zykov (1949)|}}. Una delle principali applicazioni della colorazione dei grafi, l'[[allocazione dei registri]] nei compilatori, fu introdotta nel 1981.

==Definizione e terminologia==

[[File:Graph with all three-colourings 2.svg|thumb|right|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 (teoria dei grafi)|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===
{{vedi anche|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&nbsp;+&nbsp;4⋅12&nbsp;=&nbsp;72 modi: usando tutti e quattro i colori, ci sono 4!&nbsp;=&nbsp;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:
{| class="wikitable" style="background:white;"
|-
|Colori disponibili || 1 || 2 || 3 || 4 || …
|-
|Numero di colorazioni || 0 || 0 || 12 || 72 || …
|}

Il polinomio cromatico è una funzione ''P''(''G'',&nbsp;''t'') che conta il numero di ''t''-colorazioni di&nbsp;''G''. Come indica il nome, per un dato ''G'' la funzione è in realtà un [[polinomio]] in&nbsp;''t''. Per il grafo dell'esempio, ''P''(''G'',&nbsp;''t'')&nbsp;=&nbsp;''t''(''t''&nbsp;−&nbsp;1)<sup>2</sup>(''t''&nbsp;−&nbsp;2), e infatti&nbsp;''P''(''G'',&nbsp;4)&nbsp;=&nbsp;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

: <math>\chi (G)=\min\{ k\,\colon\,P(G,k) > 0 \}.</math>

{| class="wikitable" style="background:white;"
|+Polinomi cromatici per certi grafi
|-
| Triangolo ''K''<sub>3</sub> || <math>t(t-1)(t-2)</math>
|-
| [[Grafo completo]] ''K''<sub>''n''</sub> || <math>t(t-1)(t-2) \cdots (t-(n-1))</math>
|-
| [[Albero (grafo)|Albero]] con ''n'' vertici || <math>t(t-1)^{n-1}</math>
|-
| [[Grafo ciclo|Ciclo]] ''C''<sub>''n''</sub>|| <math>(t-1)^n+(-1)^n(t-1)</math>
|-
| [[Grafo di Petersen]] || <math>t(t-1)(t-2)(t^7-12t^6+67t^5-230t^4+529t^3-814t^2+775t-352)</math>
|}

===Colorazione degli spigoli===
{{vedi anche|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'' [[Accoppiamento (teoria dei grafi)|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 [[Ponte (teoria dei grafi)|privo di ponti]] ammette una colorazione di Tait.

===Colorazione totale===
{{vedi anche|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ì

: <math>1 \le \chi(G) \le n.\,</math>

I soli grafi che possono essere 1-colorati sono i [[Grafo nullo|grafi privi di ponti]]. Un [[grafo completo]] <math>K_n</math> di ''n'' vertici richiede <math>\chi(K_n)=n</math> colori. In colorazione ottimale ci deve essere almeno uno degli ''m'' spigoli del grafo tra ogni coppia di classi di colore, così

: <math>\chi(G)(\chi(G)-1) \le 2m.\,</math>

Se ''G'' contiene una [[Cricca (teoria dei grafi)|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:

: <math>\chi(G) \ge \omega(G).\,</math>

Per i [[Grafo d'intervallo|grafi d'intervallo]] questo limite è stretto.

I grafi 2-colorabili sono esattamente i [[Grafo bipartito|grafi bipartiti]], che includono gli [[Albero (grafo)|alberi]] e le foreste. Per il teorema dei quattro colori, ogni grafo planare può essere 4-colorato.

Una [[colorazione golosa|colorazione greedy]] mostra che ogni grafo può essere colorato con un colore in più del grado massimo dei vertici,

: <math>\chi(G) \le \Delta(G) + 1. \,</math>

I grafi completi hanno <math>\chi(G)=n</math> e <math>\Delta(G)=n-1</math>, e i [[Grafo ciclo|cicli dispari]] hanno <math>\chi(G)=3</math> e <math>\Delta(G)=2</math>, così per questi grafi questo limite è il migliore possibile. In tutti gli altri casi, il limite può essere leggermente migliorato; il [[teorema di Brooks]]<ref>{{cita|Brooks (1941)||Brooks1941}}.</ref> afferma che
: '''Teorema di Brooks: '''<math>\chi (G) \le \Delta (G) </math> 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 [[Grafo di Mycielski|grafi di Mycielski]].
: '''Teorema di Mycielski''' ({{cita|Zykov (1949)|}}, {{cita|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 (teoria dei grafi)|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]] <math>L(G)</math>, e viceversa. Così,

:<math>\chi'(G)=\chi(L(G)). \, </math>

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

: <math>\chi'(G) \ge \Delta(G).\,</math>

Inoltre,

: '''[[Teorema di König (teoria dei grafi)|Teorema di König]]:''' <math>\chi'(G) = \Delta(G)</math> 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 <math>\Delta</math> ha numero cromatico degli spigoli <math>\Delta</math> o <math>\Delta+1</math>.

===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]] ({{cita|Nešetřil & Ossona de Mendez (2012)|}}).

Per i grafi planari, le colorazioni dei vertici sono essenzialmente duali per i [[Flusso zero in nessun luogo|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 (teoria dei grafi)|teorema di de Bruijn–Erdős]] ({{cita|de Bruijn & Erdős (1951)|}}).
* Se un grafo ammette una ''n''-colorazione piena per ogni ''n'' ≥ ''n''<sub>0</sub>, esso ammette una colorazione piena infinita {{cita|(Fawcett (1978)|}}.

===Problemi aperti===
Il [[Problema di Hadwiger–Nelson|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 (teoria dei grafi)|congettura di Hadwiger]] che afferma che ogni grafo con numero cromatico ''k'' ha un [[grafo completo]] su ''k'' vertici come [[Minore dei grafi|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 (teoria dei grafi)|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 <math>P(G,t)</math> non ha zeri nella regione <math>[4,\infty)</math>. Anche se è noto che tale polinomio cromatico non ha zeri nella regione <math>[5,\infty)</math> e che <math>P(G,4) \neq 0</math>, 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==
{{Infobox
| TitoloInt = Colorazione dei grafi
| immagine = [[Image:3-coloringEx.svg]]
| StileNome = font-weight:normal
| StileGruppo = background: #DD9
| StileTitoloInt = background: #DD9

| Gruppo1 = Decisione
| Nome2 = Nome
| Valore2 =Colorazione dei grafi, ''k''-colorazione
| Nome3 = Entrata
| Valore3 =Grafo ''G'' con ''n'' vertici. ''k'' intero
| Nome4 = Uscita
| Valore4 = ''G'' ammette una colorazione dei vertici esatta con ''k'' colori?
| Nome5 = Tempo di esecuzione
| Valore5 =O(2<sup> ''n''</sup>''n'')<ref name="bhk"/>
| Nome6 = Complessità
| Valore6 =[[NP-completo]]
| Nome7 = Riduzione da
| Valore7 =[[Soddisfacibilità booleana#3-soddisfacibilità|3-soddisfacibilità]]
| Nome8 = Garey–Johnson
| Valore8 =GT4

| Gruppo9 = Ottimizzazione
| Nome10 = Nome
| Valore10 = Numero cromatico
| Nome11 = Entrata
| Valore11 = Grafo ''G'' con ''n'' vertici
| Nome12 = Uscita
| Valore12 =χ(''G'')
| Nome13 = Complessità
| Valore13 =[[NP-difficile]]
| Nome14 = Approssimabilità
| Valore14 = O(''n'' (log ''n'')<sup>−3</sup>(log log ''n'')<sup>2</sup>)
| Nome15 = Inapprossimabilità
| Valore15 = O(''n''<sup>1−ε</sup>) a meno che [[Classi di complessità P e NP|P&nbsp;=&nbsp;NP]]

| Gruppo16 = Problema di conteggio
| Nome17 = Nome
| Valore17 =Polinomio cromatico
| Nome19 = Entrata
| Valore19 =Grafo ''G'' con ''n'' vertici. ''k'' intero
| Nome20 = Uscita
| Valore20 = Il numero ''P''&nbsp;(''G'',''k'') di ''k''-colorazioni esatte di ''G''
| Nome21 = Tempo di esecuzione
| Valore21 =O(2<sup> ''n''</sup>''n'')
| Nome22 = Complessità
| Valore22 =[[Sharp-P-completo|#P-completo]]
| Nome23 = Approssimabilità
| Valore23 =[[FPRAS]] per casi ristretti
| Nome24 = Inapprossimabilità
| Valore24 =Nessun [[Schema di approssimazione del tempo polinomiale|PTAS]] a meno che P&nbsp;=&nbsp;NP
}}

===Tempo polinomiale===
Determinare se un grafo può essere colorato con 2 colori è equivalente a determinare se il grafo è o no [[Grafo bipartito|bipartito]], e perciò computabile in [[Tempo lineare (algoritmo)|tempo lineare]] usando la [[ricerca in ampiezza]]. Più generalmente, il numero cromatico e una colorazione corrispondente di [[Grafo perfetto|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 <math>k^n</math> 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 <math>k=1,\ldots,n-1</math>, poco pratica per tutti tranne i più piccoli grafi in entrata.

Usando la [[programmazione dinamica]] e un limite al numero di [[Insieme indipendente (teoria dei grafi)|insiemi indipendenti massimali]], la ''k''-colorabilità può essere deciso nel tempo e nello spazio <math>O(2,445^n)</math>.<ref>{{cita|Lawler (1976)|}}.</ref> Usando il [[principio di inclusione-esclusione]] e l'algoritmo di [[Samuel Yates|Yates]] per la trasformata zeta veloce, la ''k''-colorabilità può essere decisa nel tempo <math>O(2^nn)</math><ref name="bhk">{{cita|Björklund, Husfeldt & Koivisto (2009)|}}.</ref> per qualsiasi ''k''. Gli algoritmi più veloci sono noti per la 3- e la 4-colorabilità, che può essere decisa nel tempo <math>O(1,3289^n)</math><ref>{{cita|Beigel & Eppstein (2005)|}}.</ref> e <math>O(1,7272^n)</math>,<ref>{{cita|Fomin, Gaspers & Saurabh (2007)}}.</ref> rispettivamente.

===Contrazione===
La [[Contrazione (teoria dei grafi)|contrazione]] <math>G/uv</math> 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]]:
:<math>\chi(G) = \text{min} \{  \chi(G+uv), \chi(G/uv)\}</math>
dovuta a {{cita|Zykov (1949)|}},
dove ''u'' e ''v'' sono vertici non adiacenti, <math>G+uv</math> è il grafo <math>uv</math> 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
:<math>P(G-uv, k)= P(G/uv, k)+ P(G, k)</math>
dove ''u'' e ''v'' vertici adiacenti e <math>G-uv</math> è il grafo con lo spigolo <math>uv</math> rimosso. <math>P(G - uv, k)</math> 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 [[William Thomas Tutte|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 <math>((1+\sqrt{5})/2)^{n+m}=O(1,6180^{n+m})</math> per ''n'' vertici ed ''m'' spigoli.<ref>{{cita|Wilf (1986)|}}.</ref> L'analisi può essere migliorata entro un fattore polinomiale del numero <math>t(G)</math> degli [[Albero ricorrente (matematica)|alberi ricoprenti]] del grafo in entrata.<ref>{{cita|Sekine, Imai & Tani (1995)|||}}.</ref> In pratica, si impiegano le strategie ''[[branch and bound]]'' e la reiezione dell'[[Isomorfismo|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===
{{vedi anche|Colorazione greedy}}
[[File:Greedy colourings.svg|thumb|right|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 <math>n/2</math> colori.]]

L'[[algoritmo greedy]] considera i vertici in un ordine specifico <math>v_1</math>, ...,<math> v_n</math> e assegna a <math>v_i</math> il più piccolo colore disponibile non utilizzato dai vicini di <math>v_i</math> tra <math>v_1</math>, ...,<math> v_{i-1}</math>, 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 [[Lingua inglese|inglese]] ''greedy coloring'') con il numero ottimale di <math>\chi(G)</math> 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 <math>n/2</math> colori.

Se i vertici <math> v_i </math> sono ordinati secondo il loro [[Grado (teoria dei grafi)|grado]] <math> d(v_i) </math>, la colorazione greedy risultante usa al massimo <math>{\displaystyle \max_{i}} (\text{min}
\{d(v_i ) + 1, i\})</math> colori, al massimo uno in più del grado massimo del grafo. Questa euristica è chiamata talvolta algoritmo di Welsh–Powell.<ref>{{cita|Welsh & Powell (1967)|}}.</ref> Un'altra euristica dovuta a [[Daniel Brélaz|Brélaz]] stabilisce l'ordinamento dinamicamente mentre procede l'algoritmo, scegliendo poi il vertice adiacente al maggior numero di colori diversi.<ref>{{cita|Brélaz (1979)|}}.</ref> 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 [[Calcolo distribuito#Modelli|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.<ref name="Schneider 2010">{{cita|Schneider (2010)||Schneider2010}}.</ref>

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., Δ&nbsp;+&nbsp;1. Più colori si impiegano, per es. O(Δ) invece di Δ&nbsp;+&nbsp;1, meno sessioni di comunicazioni sono richieste.<ref name="Schneider 2010"/>

Una versione diretta distribuita della versione dell'algoritmo greedy per (Δ&nbsp;+&nbsp;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''-[[Grafo ciclo|ciclo]]. Richard Cole e [[Uzi Vishkin]]<ref>{{cita|Cole & Vishkin (1986)|||}}, vedi anche {{cita|Cormen, Leiserson & Rivest (1990)|Sezione 30.5}}</ref> mostrano che c'è un algoritmo distribuito che riduce il numero dei colori da ''n'' a ''O''(log&nbsp;''n'') in un unico passo di comunicazione sincrono. Iterando la stessa procedura, è possibile ottenere una 3-colorazione di un ''n''-ciclo in ''O''(log*&nbsp;''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. {{cita|Linial (1992)||Linial1992}} mostrò che questo non è possibile: qualsiasi algoritmo deterministico distribuito richiede Ω([[log*]]&nbsp;''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*&nbsp;''n'').<ref>{{cita|Goldberg, Plotkin & Shannon (1988)|}}.</ref> La tecnica fu estesa ai [[Grafo con dischi unitari|grafi con dischi unitari]] di Schneider et al.<ref>{{cita|Schneider (2008)|}}.</ref> Gli algoritmi deterministici più veloci per la (Δ&nbsp;+&nbsp;1)-colorazione di un piccolo Δ sono dovuti a Leonid Barenboim, Michael Elkin e Fabian Kuhn.<ref>{{cita|Barenboim & Elkin (2009)|}}; {{cita|Kuhn (2009)|}}</ref> L'algoritmo di Barenboim et al. si svolge nel tempo ''O''(Δ)&nbsp;+&nbsp;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.<ref>{{cita|Panconesi (1995)|}}.</ref> usano le somposizioni a rete per computare una Δ+1 colorazione nel tempo <math> 2
^{O(\sqrt{\log n})} </math>.

Anche il problema della colorazione degli spigoli è stato studiato nel modello distribuito. {{cita|Panconesi & Rizzi (2001)|}} ottengono in questo modello una (2Δ&nbsp;−&nbsp;1)-colorazione nel tempo ''O''(Δ&nbsp;+&nbsp;log*&nbsp;''n''). Il limite inferiore per la colorazione distribuita dei vertici dovuta a {{cita|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 {{cita|Leith (2006)|}} e {{cita|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''&nbsp;=&nbsp;1 e ''k''&nbsp;=&nbsp;2. In particolare, è NP-difficile computare il numero cromatico.<ref>{{cita|Garey, Johnson & Stockmeyer (1974)|}};  {{cita|Garey & Johnson (1979)|}}.</ref> Il problema della 3-colorazione rimane NP-completa anche sui [[Gafo planare|grafi planari]] di grado 4.<ref>{{cita|Dailey (1980)|}}.</ref>

L'[[algoritmo di approssimazione]] più noto computa una colorazione di dimensione almeno entro un fattore O(''n''(log&nbsp;n)<sup>−3</sup>(log&nbsp;log&nbsp;''n'')<sup>2</sup>) del numero cromatico.<ref>{{cita|Halldórsson (1993)|}}.</ref> Per tutti gli ''ε''&nbsp;>&nbsp;0, approssimare il numero ''n''<sup>1−''ε''</sup> è [[NP-difficile]].<ref>{{cita|Zuckerman (2007)|}}.</ref>

È anche NP-difficile colorare un grafo 3-colorabile con 4 colori<ref>{{cita|Guruswami & Khanna (2000)|}}.</ref> e un grafo ''k''-colorabile con ''k''<sup>(log ''k'')&nbsp;/&nbsp;25</sup> colori per una costante ''k'' sufficientemente grande.<ref>{{cita|Khot (2001)|}}.</ref>

Computare i coefficienti del polinomio cromatico è [[Sharp-P-completo|#P-difficile]]. Infatti, anche computare il valore di <math>\chi(G,k)</math> è #P-difficile in un qualsiasi [[punto razionale]] ''k'' eccetto per ''k''&nbsp;=&nbsp;1 e ''k''&nbsp;=&nbsp;2.<ref>{{cita|Jaeger, Vertigan & Welsh (1990)|}}.</ref> Non c'è nessun [[Schema di approssimazione in temo polinomiale|FPRAS]] (schema di approssimazione in tempo pienamente polinomiale) per stimare il polinomio cromatico in un qualsiasi punto razionale ''k''&nbsp;≥&nbsp;1,5 eccetto per ''k''&nbsp;=&nbsp;2 a meno che [[NP (complessità)|NP]]&nbsp;=&nbsp;[[RP (complessità)|RP]].<ref>{{cita|Goldberg & Jerrum (2008)|}}.</ref>

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.<ref>{{cita|Holyer (1981)|}}.</ref> 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&nbsp;−&nbsp;''ε''&nbsp;) per un qualsiasi ''ε&nbsp;>&nbsp;0'' a meno che [[Classi di complessità P e NP|P&nbsp;=&nbsp;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.<ref>{{cita|Crescenzi & Kann (1998)|}}.</ref>

==Applicazioni==

===Schedulazione===

La colorazione dei vertici fa da modello a numerosi problemi di schedulazione.<ref>{{cita|Marx| (2004)||Marz (2004)}}.</ref> 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 [[Ampiezza di banda|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===
{{vedi anche|Allocazione dei registri}}

Un [[compilatore]] è un [[Programma (informatica)|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 [[Registro (informatica)|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.<ref>{{cita|Chaitin (1982)|}}.</ref> 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===

{{vedi anche|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 [[Grafo dell'amicizia|teorema dell'amicizia]], che afferma che in qualsiasi colorazione degli spigoli di <math>K_6</math> 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===
{{Colonne}}
; [[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 [[Stella (teoria dei grafi)|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''
{{Colonne spezza}}
; [[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
; [[Profondità degli alberi|Colorazione centrata]]: Ogni [[sottografo indotto]] connesso ha un colore che si è usato esattamente una volta
{{Colonne fine}}

La colorazione può essere considerata anche per i [[Grafo con segni|grafi con segni]] con i [[Grafo di guadagno|grafi di guadagno]].

== Note ==
<references/>

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

==Altri progetti==
{{interprogetto|preposizione=sulla}}

==Collegamenti esterni==
* {{Collegamenti esterni}}
* {{FOLDOC|graph colouring|graph colouring}}
* {{en}} [https://web.archive.org/web/20080412010530/http://www.cs.ualberta.ca/~joe/Coloring/index.html ''Graph Coloring Page''] by Joseph Culberson (graph coloring programs)
* {{en}} [http://vispo.com/software ''CoLoRaTiOn''] by Jim Andrews and Mike Fellows is a graph coloring puzzle
* {{cita web|1=http://www.adaptivebox.net/research/bookmark/gcpcodes_link.html|2=Links to Graph Coloring source codes|lingua=en|accesso=15 febbraio 2014|dataarchivio=4 luglio 2008|urlarchivio=https://web.archive.org/web/20080704082406/http://www.adaptivebox.net/research/bookmark/gcpcodes_link.html|urlmorto=sì}}
* {{en}} [http://www.mcs.vuw.ac.nz/~djp/tutte/ Code for efficiently computing Tutte, Chromatic and Flow Polynomials] {{Webarchive|url=https://web.archive.org/web/20080416050948/http://www.mcs.vuw.ac.nz/~djp/tutte/ |date=16 aprile 2008 }} by Gary Haggard, David J. Pearce and Gordon Royle
* {{cita web|1=https://graph-coloring.appspot.com/|2=Graph Coloring Web Application|lingua=en|accesso=30 aprile 2019|dataarchivio=6 maggio 2019|urlarchivio=https://web.archive.org/web/20190506105345/http://graph-coloring.appspot.com/|urlmorto=sì}}

{{Controllo di autorità}}
{{Portale|Matematica|informatica}}

[[Categoria:Problemi computazionali nella teoria dei grafi]]
[[Categoria:Problemi NP-completi]]