Vizualizare sursă pentru „Colorarea grafurilor”

[[Fișier:Petersen_graph_3-coloring.svg|dreapta|miniatura|O bună colorare a nodurilor grafului Petersen cu 3 culori, numărul minim posibil.]]
În [[teoria grafurilor]], '''colorarea grafurilor''' este un caz special de etichetare a grafurilor; este o atribuire de etichete numite în mod tradițional „culori” elementelor unui [[graf]], supusă anumitor constrângeri. În forma sa cea mai simplă, este o modalitate de colorat vârfurile unui graf astfel încât să nu existe două [[Nod (teoria grafurilor)|noduri]] adiacente cu aceeași culoare; aceasta se numește '''colorarea nodurilor'''. În mod similar, o colorare a muchiilor atribuie o culoare fiecărei muchii, astfel încât nu există două muchii adiacente de aceeași culoare, și o '''colorare a fețelor''' unui graf planar care atribuie o culoare pentru fiecare față sau regiune, astfel încât nu există două fețe care împart o graniță cu aceeași culoare.

Colorarea nodurilor este punctul de plecare al subiectului, alte probleme de colorat putând fi transformate într-o versiune de colorare a nodurilor. De exemplu, o colorare a muchiilor unui graf este doar o colorare a nodurilor {{Ill-wd|Q1378376|3=grafului muchiilor sale}}, și o colorare a fețelor unui [[graf planar]] este doar o colorare a nodurilor {{Ill-wd|Q2294516|3=dualului}} său. Cu toate acestea, adesea se enunță și se studiază ''ca atare'' și probleme de colorare a altceva decât noduri. Aceasta, parțial, pentru perspectivă, și parțial pentru că unele probleme sunt cel mai bine studiate în forma lor netransformată în colorare de noduri, ca, de exemplu, colorarea muchiilor.

Convenția de a folosi culori provine de colorarea țărilor pe o hartă politică, unde fiecare față este literalmente colorată. Aceasta a fost generalizată la colorarea fețelor unui grafic {{Ill-wd|Q5597085|3=încorporat}} în plan. Prin dualitate planară, el ajunge colorare a nodurilor, iar în această formă se generalizează la toate grafurile. În matematică și în reprezentările pe calculator, în mod tipic se utilizează primele numere întregi pozitive sau nenegative drept „culori”. În general, se poate folosi orice mulțime finită ca „mulțime de culori”. Natura problemei colorării depinde de numărul de culori, și nu de aspectul lor vizual.

Colorarea grafurilor se bucură de multe aplicații practice, precum și de provocări teoretice. Pe lângă tipurile clasice de probleme, se pot stabili și diferite limitatări asupra grafului, sau asupra felului cum se atribuie o culoare, sau chiar asupra culorii însăși. A devenit populară și pentru publicul general, sub forma popularului puzzle cu numere [[Sudoku]]. Colorarea grafurilor este încă un domeniu activ de cercetare.

== Istorie ==
Primele rezultate despre colorarea grafurilor tratează aproape exclusiv cu [[Graf planar|grafurile planare]] sub forma problemei colorării ''hărților''.
În timp ce încerca să coloreze o hartă a comitatelor Angliei, {{Ill-wd|Q1441533}} a postulat [[Teorema celor patru culori|conjectura celor patru culori]], în care remarca faptul că patru culori sunt suficiente pentru a colora o hartă, astfel încât regiunile care au frontieră comună să primească culori diferite. Fratele lui Guthrie a transmis întrebarea profesorului său de matematică, [[Augustus De Morgan|Augustus de Morgan]] de la [[University College London|University College]], care a menționat-o într-o scrisoare adresată lui [[William Rowan Hamilton|William Hamilton]] în 1852. [[Arthur Cayley]] a ridicat problema la o reuniune a {{Ill-wd|Q1810244}} din 1879. În același an, {{Ill-wd|Q370037}} a publicat o lucrare care a susținut că a găsit rezultatul, și timp de un deceniu problema celor patru culori a fost considerată rezolvată. Pentru realizarea lui, Kempe a fost ales membru al [[Royal Society]] și mai târziu președinte al London Mathematical Society.<ref>M. Kubale, ''History of graph coloring'', in {{harvtxt|Kubale|2004}}</ref>

În 1890, {{Ill-wd|Q1384937}} a arătat că argumentul lui Kempe era greșit. Cu toate acestea, în această lucrare, el a demonstrat teorema celor cinci culori, care spune că orice hartă în plan poate fi colorată cu nu mai mult de ''cinci'' culori, folosind ideile lui Kempe. În secolul următor, s-a depus multă muncă și s-au dezvoltat multe ipoteze pentru a reduce numărul de culori la patru, până când teorema celor patru culori a fost în cele din urmă demonstrată în 1976 de către {{Ill-wd|Q224787}} și {{Ill-wd|Q65082}}. Demonstrația s-a întors la ideile lui Heawood și Kempe și a ignorat în mare măsură evoluțiile din răstimp.<ref>{{harvtxt|van Lint|Wilson|2001|loc=Chap. 33}}</ref> Demonstrația teoremei celor patru culori este remarcabilă și pentru că este prima demonstrație matematică în mare parte asistată de calculator.

În 1912, [[George David Birkhoff]] a introdus {{Ill-wd|Q1087609|3=polinoamele cromatice}} pentru a studia problemele de colorare, care au fost generalizate la {{Ill-wd|Q7857002|3=polinomul Tutte}} de către {{Ill-wd|Q1391861}}, structuri importante din [[teoria algebrică a grafurilor]]. Kempe a atras deja atenția asupra cazului general, neplanar în 1879,<ref>{{harvtxt|Jensen|Toft|1995}}, p. 2</ref> și au urmat în secolul al XX-lea mai multe rezultate pe generalizări ale grafurilor planare care colorează suprafețe de ordin superior.

În 1960, {{Ill-wd|Q551830}} a formulat o altă conjectură despre colorarea grafurilor, ''conjectura tare a grafurilor perfecte'', motivat inițial de un concept [[Teoria informației|informatic]] numit capacitate de eroare zero a unui graf, introdusă de [[Claude Shannon|Shannon]]. Conjectura a rămas nerezolvată timp de 40 de ani, până când a fost încetățenită ca {{Ill-wd|Q17156804|3=teorema tare a grafului perfect}} de către {{Ill-wd|Q528763|3=Chudnovsky}}, {{Ill-wd|Q1531456|3=Robertson}}, {{Ill-wd|Q1396427|3=Seymour}}, și {{Ill-wd|Q2159915|3=Thomas}} în 2002.

Colorarea grafurilor a fost studiată și ca problemă algoritmică încă de la începutul anilor 1970: problema numărului cromatic este una din [[Cele 21 de probleme NP-complete ale lui Karp|cele 21 de probleme 21 NP-complete ale lui Karp]] din 1972, și în aproximativ în același timp au fost dezvoltați diverși algoritmi în timp exponențial pe baza backtrackingului și pe recurența ștergere-contracție a lui {{harvtxt|Zykov|1949}}. Una dintre cele mai importante aplicații ale colorării grafurilor, {{Ill-wd|Q1343660|3=alocarea de registre}} în compilatoare, a fost introdusă în 1981.

== Definiție și terminologie ==
[[Fișier:Graph_with_all_three-colourings_2.svg|dreapta|miniatura|Acest graf poate fi 3-colorat în 12 moduri diferite.]]

=== Colorarea nodurilor ===
Atunci când este utilizată fără nici o calificare, '''colorarea''' unui graf este aproape întotdeauna o ''bună colorare a nodurilor'', și anume o etichetare a nodurilor grafului cu culori, astfel încât să nu existe două noduri care împart aceeași [[Glosar de teoria grafurilor|muchie]] și au aceeași culoare. Întrucât un nod cu o {{Ill-wd|Q512604|3=buclă}} (adică o muchie care duce direct înapoi la el însuși) nu poate fi colorat corespunzător, se înțelege că grafurile în acest context sunt fără bucle.

Terminologia de a folosi ''culori'' pentru etichetele nodurilor datează de la problema colorării hărților. Etichete cum ar fi ''roșu'' și ''albastru'' sunt utilizate numai atunci când numărul de culori este mic, și în mod normal, se înțelege că etichetele sunt extrase din numerele întregi {1, 2, 3, ...}.

O colorare folosind cel mult ''k'' culori se numeste o '''''k''-colorare''' (bună).
Cel mai mic număr de culori necesare pentru a colora un graf ''G'' se numește '''număr cromatic''', și este adesea notat χ(''G''). Uneori se folosește și notația γ(''G''), deoarece χ(''G'')  mai poate însemnași [[Caracteristică Euler|caracteristica Euler]] a unui graf.
Un grafic căruia i se poate atribui o ''k''-colorare (bună) este ''' ''k''-colorabil''', și este ''' ''k''-cromatic''' dacă numărul său cromatic este exact ''k''.
O submulțime de noduri care au atribuite aceeași culoare se numește ''clasă de culoare'', fiecare astfel de clasă formând o mulțime independentă. Astfel, o ''k''-colorare este același lucru cu o partiție a mulțimii de noduri în ''k'' mulțimi independente, și deci termenii ''k-partit'' și ''k-colorabil'' sunt echivalenți.

=== Polinom cromatic ===
[[File:Chromatic polynomial of all 3-vertex graphs.png|thumb|upright|Toate grafurile neizomorfe de 3 noduri și polinoamele lor cromatice. Graful vid ''E''<sub>3</sub> (red) admite o 1-colorare, celelalte nu. Graful verde admite 12 colorări cu 3 culori.]]

'''Polinomul cromatic''' numară modurile în care un graf poate fi colorat folosind nu mai mult de un anumit număr de culori. De exemplu, folosind trei culori, graful din imaginea alăturată poate fi colorat în 12 moduri. Cu doar două culori, el nu ar putea fi colorat deloc. Cu patru culori, acesta poate fi colorat în 24 + 4⋅12 = 72 moduri: folosind toate cele patru culori, sunt 4! = 24 colorări valide (''fiecare'' atribuire de patru culori pentru ''orice'' graf cu 4 noduri este o bună colorare); și, pentru fiecare alegere de trei din cele patru culori, sunt valide 12 3-colorări. Astfel, pentru graful din exemplu, un tabel cu numărul colorări valide ar începe așa:
{| class="wikitable" style="background: url(&quot;data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAABAAAAAQCAYAAAAf8/9hAAAALHRFWHRDcmVhdGlvbiBUaW1lAEZyaSAxMiBOb3YgMjAxMCAxOTowNzowMiArMTIwMOGr8p4AAAAHdElNRQfaCwwGBxwduq16AAAACXBIWXMAAAsSAAALEgHS3X78AAAABGdBTUEAALGPC/xhBQAAAfJJREFUeNqVkk1vElEUhp87X4CIFhhMG0toMC5K3Lgxbro10bhxY2Jc+CO666Y/oP/DxFVjTKM7l1apTdM0JSU0LSg0WqaUjwE6MDNebGpKBYlndc+55zw5H6/gim2UUd0qs5Uy6VaTa7EYdtOmUN7naHER92q+dtnZ2UFpHTOTXWfuwxrfYlNUHz1lxvdIVyx6MuXHPwFeBLW2z+29Pepr7ziUof7SEq1CibCEmKMAymXH6SD6LrpzRndQPIjNz9P3odu2URlhQ4C+ghcM0JpLEchkzrv7eIDS62JYP2lPBJS2cIMhyrMpwo+fMbW8jLhhc2t3F906pjoK8GcH29vonoenRDk1m5zcvUM6ZuJvZEnmcljT09hbR6iVIuLJw/PxhgAOPOj26Gk1nEQCNWAQ7XS4bxvw8hWuGedeo4iR+/y7+OtfgM1N9OIBwnFQ5SLdZJJ2JML17BdqEuYHgmiahsjnx4zw/i2fslm8dht/YQHx/AWpfI50/ZTKm9d8lykiHkf4/hjA6ipnF++VFRS7T1AoaDejyCEYlHmWNeEKF9YISz30CBkGirxKUIZGamAsQG2hux66BAipi1A6g/5fAM/HkGrUFfmr6wSSiWHJTwQoPrq8hCYEGDoh0xzfwUhyIY9ROkRrNKQ65e1P6uM7+AW+ibcHEM1ixAAAAABJRU5ErkJggg==&quot;) 268px 0px no-repeat white; margin-bottom: 10px;"
|Culori disponibile 
| 1 
| 2 
| 3 
| 4 
| ...
|-
|Numărul de colorări
| 0 
| 0 
| 12 
| 72 
| ...
|}
Polinomul cromatic este o funcție ''P''(''G'', ''t'') care contorizează numărul de ''t''-colorări ale lui&nbsp;''G''. După cum indică și numele, pentru un ''G'' dat, funcția este într-adevăr un [[polinom]] în ''t''. Pentru graful luat ca exemplu, ''P''(''G'', ''t'') = ''t''(''t'' &#x2212; 1)<sup>2</sup>(''t'' &#x2212; 2), și într-adevăr, ''P''(''G'', 4) = 72.

Polinomul cromatic include cel puțin la fel de multe informații despre colorabilitatea lui ''G'' ca și numărul cromatic. Într-adevăr, χ este cel mai mic număr întreg pozitiv care nu este rădăcină a polinomului cromatic
: <math>\chi (G)=\min\{ k\,\colon\,P(G,k) > 0 \}.</math>
{| class="wikitable" style="background: none 0% 0% repeat white; margin-bottom: 32px;"
|+Polinoame cromatice pentru anumite grafuri
| Triunghiul ''K''<sub>3</sub> 
| <math>t(t-1)(t-2)</math>
|-
|[[Graf complet|Graful complet]] ''K''<sub>''n''</sub> 
| <math>t(t-1)(t-2) \cdots (t-(n-1))</math>
|-
| [[Arbore (teoria grafurilor)|Arbore]] cu ''n'' noduri 
| <math>t(t-1)^{n-1}</math>
|-
| {{Ill-wd|Q622506|3=Ciclul}} ''C''<sub>''n''</sub>
| <math>(t-1)^n+(-1)^n(t-1)</math>
|-
|[[Graful lui Petersen|Graful Petersen]]
| <math>t(t-1)(t-2)(t^7-12t^6+67t^5-230t^4+529t^3-814t^2+775t-352)</math>
|}

=== Colorarea muchiilor ===
O '''colorare a muchiilor''' unui graf este o bună colorare a ''muchiilor'', adica o atribuire de culori muchiilor astfel încât să niciun nod nu este incident la două muchii de aceeași culoare. O colorare de muchii cu ''k'' culori se numește ''k''-colorare de muchii și este echivalentă cu problema de partiționării mulțimii muchiilor în ''k'' {{Ill-wd|Q1065144|3=cuplaje}}. Cel mai mic număr de culori necesare pentru o colorare a muchiilor unui graf ''G'' este '''indicele cromatic''', sau '''numărul cromatic al muchiilor''', ''χ''<nowiki/>'(''G''). O '''colorare Tait''' este o 3-colorare a muchiilor unui {{Ill-wd|Q1374495|3=graf cubic}}. Teorema celor patru culori este echivalentă cu afirmația că fiecare graf planar cubic [[Punte (teoria grafurilor)|fără punți]] admite o colorare Tait.

=== Colorare totală ===
'''Colorarea totală''' este un tip de colorare a nodurilor ''și'' muchiilor unui graf. Atunci când este utilizată fără nicio calificare, o colorare totală se presupune a fi mereu corectă, în sensul că nu există noduri adiacente, muchii adiacente, și nici perechi de muchii și extremități ale ei care au aceeași culoare. Numărul cromatic total ''χ"(G)'' al unui graf G este cel mai mic număr de culori necesare în orice colorare totală a lui G.

=== {{Visible anchor|Colorare neetichetată}} ===
O '''colorare neetichetată''' a unui grafic este o {{Ill-wd|Q288465|3=orbită}} a unei colorări sub acțiunea [[grup de automorfisme|grupului de automorfisme]] al grafului. Dacă am interpreta o colorare a unui graf pe <math>d</math> noduri ca un vector în <math>\mathbb{Z}^d</math>, acțiunea unui automorfism este o [[permutare]] a coeficienților de colorat.
Există analogii ale polinoamelor cromatice care numără colorările neetichetate ale unui graf dintr-o mulțime finită dată de culori.

== Proprietăți ==

=== Limite privind numărul cromatic ===
Atribuirea de culori distincte pentru noduri distincte dă mereu o buna colorare, deci
: <math>1 \le \chi(G) \le n.\,</math>
Singurele grafuri care pot fi 1-colorate sunt {{Ill-wd|Q3033506|3=grafurile fără muchii}}. Un [[graf complet]] <math>K_n</math> cu ''n'' noduri are nevoie de <math>\chi(K_n)=n</math> culori. Într-o colorare optimă trebuie să fie cel puțin una din cele ''m'' muchii ale grafului între fiecare pereche de clase de culori, deci
: <math>\chi(G)(\chi(G)-1) \le 2m.\,</math>
Dacă ''G'' conține o [[clică]] de dimensiune ''k'', atunci cel puțin ''k'' culori sunt necesare pentru colorarea acelei clici; cu alte cuvinte, numărul cromatic este cel puțin numărul de clică:
: <math>\chi(G) \ge \omega(G).\,</math>
Pentru {{Ill-wd|Q1187620|3=grafurile perfecte}} această limită este strictă.

Grafurile 2-colorabile sunt exact [[Graf bipartit|grafurile bipartite]], inclusiv [[Arbore (teoria grafurilor)|arborii]] și pădurile.
Conform teoremei celor patru culori, orice graf planar poate fi 4-colorat.

O {{Ill-wd|Q5601715|3=colorare greedy}} arată că fiecare graf poate fi colorat cu o culoare mai mult decât [[Grad (teoria grafurilor)|gradul]] maxim al unui nod,
: <math>\chi(G) \le \Delta(G) + 1. \,</math>
Grafurile complete au <math>\chi(G)=n</math> și <math>\Delta(G)=n-1</math>, și {{Ill-wd|Q622506|3=ciclurile impare}} au <math>\chi(G)=3</math> și <math>\Delta(G)=2</math>, astfel încât pentru aceste grafuri limita este cea mai bună posibilă. În toate celelalte cazuri, limita poate fi ușor îmbunătățită; {{Ill-wd|Q512897|3=teorema lui Brooks}}<ref>{{harvtxt|Brooks|1941}}</ref> prevede că
: '''Teorema lui Brooks: '''<math>\chi (G) \le \Delta (G) </math> pentru un graf conex simplu ''G'', dacă ''G'' nu este un graf complet sau ciclu impar.

=== Limitele inferioare ale numărului cromatic ===
De-a lungul anilor s-au descoperit mai multe limite inferioare pentru numărul cromatic:

'''Limita Hoffman:''' Fie <math>W</math> o matrice simetrică reală, astfel încât <math> W_{i,j} = 0 </math> ori de câte ori <math>(i,j) </math> nu este o muchie în <math>G</math>. Se definește <math>\chi_W(G) = 1 - \tfrac{\lambda_{\max}(W)}{\lambda_{\min}(W)}</math>, unde <math>\lambda_{\max}(W), \lambda_{\min}(W)</math> sunt cea mai mare și, respectiv, cea mai mică valoare proprie a lui <math>W</math>. Se definește <math> \chi_H(G) = \max_W \chi_W(G)</math>, cu <math>W</math> ca mai sus. Atunci:
: <math> \chi_H(G)\leq \chi(G)</math>.
'''{{Visible anchor|Număr cromatic de vector}}:''' Fie <math>W</math> o matrice pozitivă semidefinită astfel încât <math> W_{i,j} \le -\tfrac{1}{k-1} </math> ori de câte ori <math>(i,j) </math> este o muchie în <math>G</math>. Se definește <math>\chi_V(G)</math> ca cel mai  mic ''k'' pentru care o astfel de matrice <math>W</math> există. Atunci
: <math> \chi_V(G)\leq \chi(G)</math>.
'''{{Ill-wd|Q6692699|3=Numărul Lovász}}:''' Numărul Lovász al unui graf complementar este tot o limită inferioară pentru numărul cromatic:
: <math> \vartheta(\bar{G}) \leq \chi(G)</math>.
'''{{Ill-wd|Q5477527|3=Număr cromatic fracționar}}:''' Numărul cromatic fracționar al unui graf este o limită inferioară a numărului cromatic:
: <math> \chi_f(G) \leq \chi(G)</math>.
Aceste limite sunt ordonate după cum urmează:
: <math> \chi_H(G) \leq \chi_V(G) \leq \vartheta(\bar{G}) \leq \chi_f(G) \leq \chi(G)</math>.

=== Grafuri cu număr cromatic mare ===
Grafurile cu clici mari au un număr cromatic mare, dar reciproca nu este adevărată. {{Ill-wd|Q3115494|3=Graful Grötzsch}} este un exemplu de graf 4-cromatic fără triunghiuri, și exemplul poate fi generalizat la {{Ill-wd|Q977674|3=mycielskieni}}.
: '''Teorema lui Mycielski''' ({{harvard citations|nb|first=Alexander|last=Zykov|year=1949|authorlink=Alexander Zykov}}, {{harvard citations|nb|first=Jan|last=Mycielski|year=1955|authorlink=Jan Mycielski}}): Există grafice fără triunghiuri cu un număr cromatic arbitrar de mare.
Din teorema lui Brooks, grafurile cu număr cromatic mare trebuie să aibă gradul maxim mare. O altă proprietate locală care duce la un număr cromatic mare este prezența unei clici mari. Dar colorabilitatea nu este în întregime un fenomen local: Un graf cu calibru mare arată local ca un arbore, pentru că toate ciclurile lui sunt lungi, dar numărul cromatic nu este obligatoriu 2:
: '''Teoremă''' (Erdős): Există grafuri de calibru și număr cromatic  arbitrar de mari.

=== Limitele indicelui cromatic ===
O colorare a muchiilor lui ''G'' este o colorare a nodurilor grafului muchiilor sale <math>L(G)</math> și vice-versa. Astfel,
: <math>\chi'(G)=\chi(L(G)). \, </math>
Există o relație puternică între colorabilitatea muchiilor și gradul maxim al grafului <math>\Delta(G)</math>. Deoarece toate muchiile incidente la același nod au nevoie de propria lor colorare, avem
: <math>\chi'(G) \ge \Delta(G).\,</math>
Mai mult decât atât,
: '''Teorema lui König:''' <math>\chi'(G) = \Delta(G)</math> dacă ''G'' este bipartit.
În general, relația este mai puternică decât ceea ce dă teorema lui Brooks pentru colorarea nodurilor:
: '''Teorema lui Vizing:''' Un graf de grad maxim <math>\Delta</math> are numărul cromatic al muchiilor <math>\Delta</math> sau <math>\Delta+1</math>.

=== Alte proprietăți ===
Un graf are o ''k''-colorare [[dacă și numai dacă]] are o {{Ill-wd|Q4677986|3=orientare aciclică}} pentru care {{Ill-wd|Q2916352|3=cel mai lung drum}} are lungime cel mult ''k''; aceasta este {{Ill-wd|Q5518852|3=teorema Gallai–Hasse–Roy–Vitaver}} {{Harvard citation|Nešetřil|Ossona de Mendez|2012}}.

Pentru grafuri planare, colorările nodurilor sunt, în esență, duale cu {{Ill-wd|Q7066659|3=fluxurile nicăieri-zero}}.

Despre grafurile infinite, se știu mult mai puține.
Următoarele sunt două dintre puținele rezultate despre colorarea grafurilor infinite:
* Dacă toate subgrafurile finite ale unui [[Glosar de teoria grafurilor|graf infinit]] ''G'' sunt ''k''-colorabile, atunci și ''G ''este la fel, în ipoteza [[Axioma alegerii|axiomei alegerii]]. Aceasta este {{Ill-wd|Q3527054|3=teorema de Bruijn–Erdős}} din {{harvtxt|de Bruijn|Erdős|1951}}.
* Dacă un graf admite o ''n''-colorare deplină, pentru orice ''n'' ≥ ''n''<sub>0</sub>, admite o colorare deplină infinită {{Harvard citation|Fawcett|1978}}.

=== Probleme deschise ===
{{Ill-wd|Q1383936|3=Numărul cromatic al planului}}, unde două puncte sunt adiacente dacă au distanță unitară, este necunoscut, deși este 4, 5, 6, sau 7. Alte [[Probleme nerezolvate ale matematicii|probleme deschise]] privind numărul cromatic al grafurilor sunt {{Ill-wd|Q1128435|3=conjectura Hadwiger}} care afirmă că orice graf cu număr cromatic ''k'' are un [[graf complet]] de ''k'' noduri ca {{Ill-wd|Q905837|3=minor}}, {{Ill-wd|Q5385322|3=conjectura Erdős–Faber–Lovász}} care limitează numărul cromatic al reuniunilor de grafuri complete care au exact un nod în comun pentru fiecare pereche, și {{Ill-wd|Q4712279|3=conjectura Albertson}} că în rândul grafurilor ''k''-cromatice, grafurile complete sunt cele cu cel mai mic {{Ill-wd|Q266775|3=număr de traversare}}.

Când Birkhoff și Lewis au introdus polinomul cromatic în abordarea teoremei celor patru culori, ei au presupus că pentru grafurile planare ''G'', polinomul <math>P(G,t)</math> nu are zerouri în intervalul <math>[4,\infty)</math>. Deși se știe că un astfel de polinom cromatic nu are zerouri în intervalul <math>[5,\infty)</math> și că <math>P(G,4) \neq 0</math>, conjectura lor este încă nerezolvată. De asemenea, rămâne o problemă nerezolvată caracterizarea grafurilor care au același polinom cromatic și determinarea polinoamelor cromatice.

== Algoritmi ==

=== În timp polinomial ===
Determinarea dacă un graf poate fi colorat cu 2 culori este echivalent cu a determina dacă graful este [[Graf bipartit|bipartit]] sau nu și, astfel, este calculabilă în [[Complexitate în timp|timp liniar]] folosind [[Căutare în lățime|căutarea în lățimea]] sau [[Căutare în adâncime|căutarea în adâncime]]. Mai general, numărul cromatic și colorarea corespunzătoare a {{Ill-wd|Q1187620|3=grafurilor perfecte}} pot fi calculate în [[Complexitate în timp|timp polinomial]] folosind {{Ill-wd|Q2269096|3=programarea semidefinită}}. Se cunosc formule închise pentru polinoamele cromatice pentru multe clase de grafice, cum ar fi pădurile, grafurile cordale, ciclurile, roțile și scările, astfel încât acestea pot fi evaluate în timp polinomial.

Dacă graful este planar și are o lățime de ramificare mică (sau este neplanar dar cu o descompunere cunoscută în ramuri), atunci acesta poate fi rezolvat în timp polinomial folosind programarea dinamică. În general, timpul necesar este polinomial în raport cu dimensiunea grafului, dar exponențial în raport cu lățimea de ramificare.

=== Algoritmi exacți ===
{{Ill-wd|Q850362|3=Căutara cu forța brută}} a unei ''k''-colorări consideră fiecare dintre cele <math>k^n</math> atribuiri de ''k'' culori pentru ''n'' noduri și o verifică pe fiecare dacă este corectă. Pentru calculul numărului cromatic și al polinomului cromatic, această procedură este folosită pentru fiecare <math>k=1,\ldots,n-1</math>, fiind nepractică pentru orice graf, mai puțin cele mai mici.

Folosind {{Ill-wd|Q380679|3=programarea dinamică}} și o limită cu privire la numărul de {{Ill-wd|Q7888149|3=mulțimi independente maximale}}, ''k''-colorabilitatea poate fi decisă în timp și spațiu <math>O(2.445^n)</math>.<ref>{{harvtxt|Lawler|1976}}</ref> Folosind principiul {{Ill-wd|Q849335|3=includere–excludere}} și algoritmul lui {{Ill-wd|Q7412973|3=Yates}} pentru transformata zeta rapidă,
''k''-colorabilitatea poate fi decisă în timp <math>O(2^nn)</math><ref name="bhk">{{harvtxt|Björklund|Husfeldt|Koivisto|2009}}</ref> pentru orice ''k''. Se cunosc algoritmi mai rapizi pentru 3- și 4-colorabilitate, care pot fi deciși în timp <math>O(1.3289^n)</math><ref>{{harvtxt|Beigel|Eppstein|2005}}</ref> și, respectiv, <math>O(1.7272^n)</math><ref>{{harvtxt|Fomin|Gaspers|Saurabh|2007}}</ref>

=== Contracția ===
Contracția <math>G/uv</math> a unui graf ''G'' este graful obținut prin identificarea nodurilor ''u'' și ''v'', și eliminarea oricăror muchii între ele. Muchiile rămase și care erau inițial incidente la ''u'' sau la ''v'' sunt acum incidente la identificarea lor. Această operațiune joacă un rol major în analiza colorării grafurilor.

Numărul cromatic care satisface [[Relație de recurență|relația de recurență]]:
: <math>\chi(G) = \text{min} \{  \chi(G+uv), \chi(G/uv)\}</math>
conform {{harvtxt|Zykov|1949}},
unde ''u'' și ''v'' sunt noduri neadiacente, și <math>G+uv</math> este graful la care se adaugă muchia <math>uv</math>. Mai mulți algoritmi se bazează pe evaluarea acestei recurențe și arborele de calcul rezultat se numește uneori arbore Zykov. Timpul de funcționare se bazează pe o euristică pentru alegerea nodurilor ''u'' și ''v''.

Polinomul cromatic satisface următoarea relație de recurență
: <math>P(G-uv, k)= P(G/uv, k)+ P(G, k)</math>
unde ''u'' și ''v'' sunt noduri adiacente, și <math>G-uv</math> este graful cu muchia <math>uv</math> eliminată. <math>P(G - uv, k)</math> reprezintă numărul de bune colorări posibile ale grafului, unde nodurile pot avea culori la fel sau identice. Atunci bunele colorări apar din două grafuri diferite. Aceasta deoarece, dacă nodurile ''u'' și ''v'' au culori diferite, atunci s-ar putea la fel de bine să se ia în considerare un graf unde ''u'' și ''v'' sunt adiacente. Dacă ''u'' și ''v'' au aceleași culori, s-ar putea considera un graf unde ''u'' și ''v'' sunt contractate. Curiozitatea lui {{Ill-wd|Q1391861}} despre ce alte proprietăți ale grafului satisfac această recurență l-a condus la descoperirea unei generalizări bivariate a polinomului  cromatic, {{Ill-wd|Q7857002|3=polinomul Tutte}}.

Aceste expresii dau naștere unei proceduri recursive numită ''algoritmul ștergere–contracție'', care stă la baza multor algoritmi pentru colorarea grafurilor. Timpul de funcționare satisface aceeași relație de recurență ca și [[Numerele Fibonacci|numerele lui Fibonacci]], astfel încât, în cel mai rău caz algoritmul se execută într-un timp cu un factor polinomial în funcție de <math>((1+\sqrt{5})/2)^{n+m}=O(1.6180^{n+m})</math> pentru ''n'' noduri și ''m'' muchii.<ref>{{harvtxt|Wilf|1986}}</ref> Analiza poate fi îmbunătățită până la un factor polinomial de numărul <math>t(G)</math> al {{Ill-wd|Q831672|3=arborilor de acoperire}} al grafului de intrare.<ref>{{harvtxt|Sekine|Imai|Tani|1995}}</ref>
În practică, strategiile branch and bound și respingerea [[Izomorfism|izomorfismelor de graf]] se folosesc pentru a evita unele apeluri recursive. Timpul de execuție depinde de euristica folosită pentru a alege perechea de noduri.

=== Colorarea greedy ===
[[File:Greedy colourings.svg|thumb|right|Două colorări greedy ale aceluiași graf utilizând ordini diferite ale nodurilor. Exemplul din dreapta se generalizează la grafurile 2-colorabile cu ''n'' noduri, unde algoritmul greedy folosește <math>n/2</math> culori.]]
[[Algoritm greedy|Algoritmul greedy]] consideră nodurile într-o anumită ordine <math>v_1</math>,…,<math> v_n</math> și atribuie nodului <math>v_i</math> cea mai mică culoare disponibilă care nu este utilizată de vecinii lui <math>v_i</math> dintre <math>v_1</math>,…,<math> v_{i-1}</math>, adăugând o culoare nouă dacă este necesar. Calitatea colorării rezultate depinde de ordonarea aleasă. Exista o ordonare care duce la o colorare greedy cu numărul optim de <math>\chi(G)</math> culori. Pe de altă parte, colorările greedy pot fi arbitrar de rele; de exemplu, {{Ill-wd|Q3115466|3=graful coroană}} cu ''n'' noduri poate fi 2-colorat, dar are o ordonare care ar duce la o colorare greedy cu <math>n/2</math> culori.

Pentru {{Ill-wd|Q1322892|3=grafurile cordale}}, și pentru cazuri speciale de grafuri cordale, cum ar fi {{Ill-wd|Q835942|3=grafurile de interval}} și {{Ill-wd|Q3115472|3=grafurile de indiferență}}, algoritmul greedy de colorare poate fi folosit pentru a găsi o colorare optimă în timp polinomial, alegând ordonarea nodurilor pentru a fi inversă pentru o {{Ill-wd|Q1322892|3=ordonare de eliminare perfectă}} pentru graf. {{Ill-wd|Q17148818|3=Grafurile perfect ordonabile}} generalizează această proprietate, dar este NP-hard găsirea unei ordonări perfecte a acestor grafuri.

Dacă nodurile sunt ordonate după [[Grad (teoria grafurilor)|gradul]] lor, colorarea greedy rezultată folosește cele mult <math>\text{max}_i \text{ min}
\{d(x_i ) + 1, i\}</math> culori, cel mult cu una mai mult decât gradul maxim al grafului. Această euristică este uneori numită algoritmul Welsh–Powell.<ref>{{harvtxt|Welsh|Powell|1967}}</ref> O altă euristică datorată lui Brélaz stabilește ordonarea dinamică pe măsură ce avansează algoritmul, alegând următorul nod ca fiind cel adiacent cu cel mai mare număr de culori diferite.<ref>{{harvtxt|Brélaz|1979}}</ref> Multe alte euristici de colorare a grafului se bazează similar pe colorarea greedy pentru o anumită strategie statică sau dinamică de a ordona nodurile, acești algoritmi sunt uneori numiți algoritmi de '''colorare secvențială'''.

Numărul maxim (cel mai rău) de culori care pot fi obținute prin algoritmul greedy, folosind o ordonare a nodurilor aleasă pentru a maximiza acest număr, se numește numărul Grundy al unui graf.

=== Algoritmi paraleli și distribuiți ===
În domeniul {{Ill-wd|Q2835898|3=algoritmilor distribuiți}}, colorarea grafurilor este strâns legată de problema {{Ill-wd|Q903282|3=simetriei}}. Algoritmii state-of-the-art actuali sunt mai rapizi decât algoritmii determiniști pentru un grad maxim Δ suficient de mare. Cei mai rapizi algoritmi randomizați folosesc {{Ill-wd|Q6934515|3=tehnica mai multor încercări}} elaborată de Schneider et al.<ref name="Schneider 2010">{{harvtxt|Schneider|2010}}</ref>

Într-un graf simetric, un algoritm distribuit determinist nu poate găsi o bună colorare a nodurilor. Este nevoie de unele informații auxiliare pentru a sparge simetria. O ipoteză standard este că, inițial, fiecare nod are un ''identificator unic'', de exemplu, din mulțimea {1, 2, ..., ''n''}. Altfel spus, vom presupune că se dă o ''n''-colorare. Provocarea este de a ''reduce'' numărul de culori de la ''n'' la, de exemplu, Δ + 1. Cu cât se folosesc mai multe culori, de exemplu, O(Δ) în loc de Δ + 1, cu atât este nevoie de mai puține runde de comunicație.

O versiune distribuită simplă a algoritmului greedy pentru (Δ + 1)-colorare necesită Θ(''n'') runde de comunicare, în cel mai rău caz − se poate să fie nevoie ca informația să fie propagată dintr-o parte a rețelei în alta.

Cel mai simplu caz de interes este un ''n''-{{Ill-wd|Q622506|3=ciclu}}. Richard Cole și {{Ill-wd|Q7905027}}<ref>{{harvtxt|Cole|Vishkin|1986}}, see also {{harvtxt|Cormen|Leiserson|Rivest|1990|loc=Section 30.5}}</ref> arată că există un algoritm distribuit care reduce numărul de culori de la ''n'' la ''O''(log ''n'') într-un singur pas de comunicare sincronă. Prin iterarea aceleiași proceduri, se poate obține o 3-colorare a unui ''n''-ciclu în ''O''({{log-star}} ''n'') pași de comunicare (presupunând că avem identificatori unici pentru noduri).

Funcția {{log-star}}, un [[logaritm iterat]], este o funcție extrem de lent crescătoare, „aproape constantă”. Prin urmare, rezultatul lui Cole și Vishkin a ridicat întrebarea dacă există un algoritm distribuit în ''timp constant'' pentru 3-colorarea unui ''n''-ciclu. {{harvtxt|Linial|1992}} a arătat că acest lucru nu este posibil: orice algoritm distribuit determinist necesită Ω({{log-star}} ''n'') pași de comunicare pentru a reduce o ''n''-colorare la o 3-colorare într-un ''n''-ciclu.

Tehnica lui Cole și Vishkin poate fi aplicată și în grafuri cu grad arbitrar mărginit; timpul de funcționare este de poly(Δ) + ''O''({{log-star}} ''n'').<ref>{{harvtxt|Goldberg|Plotkin|Shannon|1988}}</ref> Tehnica a fost extinsă la {{Ill-wd|Q3115549|3=grafuri disc unitate}} de Schneider et al.<ref>{{harvtxt|Schneider|2008}}</ref> Cel mai rapid algoritm determinist pentru (Δ + 1)-colorare pentru un Δ mic se datorează lui Leonid Barenboim, Michael Elkin și Fabian Kuhn.<ref>{{harvtxt|Barenboim|Elkin|2009}}; {{harvtxt|Kuhn|2009}}</ref> Algoritmul lui Barenboim et al. rulează în timp ''O''(Δ) + {{log-star}}(''n'')/2, care este optim în termeni de ''n'' deoarece factorul constant 1/2 nu poate fi îmbunătățit din cauza limitei inferioare a lui Linial. Panconesi et al.<ref>{{harvtxt|Panconesi|1995}}</ref> utilizează descompuneri ale rețelei pentru a calcula o Δ+1 colorare în timp <math> 2^{O\left(\sqrt{\log n}\right)} </math>.

Problema colorării muchiilor a fost studiată și în modelul distribuit. {{harvtxt|Panconesi|Rizzi|2001}} ajung la o (2Δ &#x2212; 1)-colorare în timp ''O''(Δ + {{log-star}} ''n'') în acest model. Limita inferioară pentru colorarea distribuită a nodurilor dată de {{harvtxt|Linial|1992}} se aplică și la problema distribuită a colorării muchiilor.

=== Algoritmi descentralizați ===
Algoritmii descentralizați sunt cei în care nu se permite schimbul de mesaje (spre deosebire de algoritmii distribuiți unde au loc schimburi locale de mesaje), și există algoritmi eficienți și descentralizați care vor colora un graf dacă există deja o bună colorare. Acestea presupun că un nod poate simți dacă vreunul dintre vecinii săi utilizează aceeași culoare ca nodul, adică dacă există un conflict local. Aceasta este o ipoteză rezonabilă în multe aplicații, de exemplu alocarea canalelor de comunicație fără fir, este rezonabil să se presupună că o stație va fi capabilă să detecteze dacă alți transmițători interferează pe același canal (de exemplu, prin măsurarea SINR). Această culegere de informații suficiente pentru a permite algoritmi bazați pe automate care învață pentru a găsi o colorare adecvată a grafului cu o probabilitate de unu, vezi de exemplu {{harvtxt|Leith|2006}} și {{harvtxt|Duffy|2008}}.

=== Complexitatea calculului ===
Calculul colorării grafului este unul dificil. Problema de a decide dacă un anumit graf admite o ''k''-colorare pentru un anumit ''k'' este [[NP-completitudine|NP-completă]], cu excepția cazurilor ''k'' ∈ {0,1,2}. În special, calculul numărului cromatic este NP-hard.<ref>{{harvtxt|Garey|Johnson|Stockmeyer|1974}};  {{harvtxt|Garey|Johnson|1979}}.</ref>
3-colorarea rămâne NP-completă, chiar și pe [[Graf planar|grafuri planare]] 4-regulate.<ref>{{harvtxt|Dailey|1980}}</ref> ''k''-colorarea a unui graf planar este însă în P, pentru orice k>3, deoarece orice graf planar are o 4-colorare (și, prin urmare, și o k-colorare, pentru orice k≥4); a se vedea [[teorema celor patru culori]].

Cel mai cunoscut {{Ill-wd|Q621751|3=algoritm de aproximare}} calculează o colorare de dimensiune cel mult un factor de O(''n''(log n)<sup>&#x2212;3</sup>(log log ''n'')<sup>2</sup>) a numărului cromatic.<ref>{{harvtxt|Halldórsson|1993}}</ref> Pentru ''ε'' > 0, aproximarea numărului cromatic în ''n''<sup>1&#x2212;''ε''</sup> este [[NP-hard]].<ref>{{harvtxt|Zuckerman|2007}}</ref>

NP-hard este și colorarea unui graf 3-colorabil cu 4 culori<ref>{{harvtxt|Guruswami|Khanna|2000}}</ref> și a unui graf ''k''-colorabil cu ''k''<sup>(log ''k'' ) / 25</sup> de culori pentru o constantă ''k'' suficient de mare.<ref>{{harvtxt|Khot|2001}}</ref>

Calculul coeficienților polinomului cromatic este {{Ill-wd|Q841545|3=#P-hard}}. De fapt, chiar și calculul valorii <math>\chi(G,k)</math> este #P-hard în orice {{Ill-wd|Q3393476|3=punct rațional}} ''k'' , cu excepția ''k'' = 1 și ''k'' = 2.<ref>{{harvtxt|Jaeger|Vertigan|Welsh|1990}}</ref> Nu există nicio {{Ill-wd|Q843550}} pentru evaluarea polinomului cromatic în orice punct rațional ''k'' ≥ 1.5 cu excepția ''k'' = 2, dacă  [[NP (teoria complexității)|NP]] &#x2260;&nbsp;{{Ill-wd|Q1190846|3=RP}}.<ref>{{harvtxt|Goldberg|Jerrum|2008}}</ref>

Pentru colorarea muchiilor, demonstrarea rezultatului lui Vizing oferă un algoritm care folosește cel mult Δ+1 culori. Cu toate acestea, decizia între cele două valori candidate pentru numărul cromatic al muchiilor este NP-completă.<ref>{{harvtxt|Holyer|1981}}</ref> În termeni de algoritmi de aproximare, algoritmul lui Vizing arată că numărul cromatic al muchiilor poate fi aproximat într-o marjă de 4/3,
și rezultatul dificultății arată că nu există niciun (4/3 &#x2212; ''ε'' )-algoritm pentru orice ''ε > 0'' decât dacă [[Clasele de complexitate P și NP|P = NP]]. Acestea sunt printre cele mai vechi rezultate din literatura algoritmilor de aproximare, chiar dacă nicio lucrare nu utilizează explicit această noțiune.<ref>{{harvtxt|Crescenzi|Kann|1998}}</ref>

== Utilizări ==

=== Planificarea ===
Colorarea nodurilor modelează o serie de {{Ill-wd|Q1123036|3=probleme de planificare}}.<ref>{{harvtxt|Marx|2004}}</ref> În forma sa de bază, unei mulțimi date de niște sarcini trebuie să i se atribuie intervale de timp, fiecare sarcină necesitând un astfel de interval. Sarcinile pot fi programate în orice ordine, dar perechile de sarcini ar putea intra în ''conflict'' în sensul că nu li se poate atribui același interval de timp, de exemplu pentru că ambele se bazează pe o resursă comună. Graful corespunzător conține un nod pentru fiecare sarcină și o muchie pentru fiecare pereche contradictorie de sarcini. Numărul cromatic al grafului este exact la ''makespan-ul'' minim, adică timpul optim pentru a termina toate sarcinile fără conflicte.

Detalii ale problemei planificării definesc structura grafului. De exemplu, atunci când se atribuie aeronave unor zboruri, graful de conflicte rezultat este un {{Ill-wd|Q835942|3=graf de intervale}}, astfel încât problema colorării poate fi rezolvată eficient. În {{Ill-wd|Q4854763|3=alocarea lățimii de bandă}} pentru posturile de radio, graful de conflicte rezultat este un {{Ill-wd|Q3115549|3=grad disc unitate}}, astfel încât problema colorării este 3-aproximabilă.

=== Alocarea registrelor ===
Un [[compilator]] este un [[Program (informatică)|program de calculator]] care traduce un {{Ill-wd|Q629206|3=limbaj de calculator}} în altul. Pentru a îmbunătăți timpul de execuție al codului rezultat, una dintre tehnicile de optimizare a compilatoarelor este alocarea registrelor, unde cele mai frecvent utilizate valori ale programului compilat sunt stocate în [[Registru de procesor|registrele procesorului]], cel mai rapid spațiu de memorare. În mod ideal, valorilor li se atribuie registre așa încât ele să poată sta în registrele atunci când sunt utilizate.

Abordarea de manual a acestei probleme este de a modela problema ca pe o colorare a grafului.<ref>{{harvtxt|Chaitin|1982}}</ref> Compilatorul construiește astfel un ''graf de interferențe'', unde nodurile sunt variabile și o muchie conectează două noduri dacă acestea sunt necesare în același timp. Dacă graful poate fi colorat cu ''k'' culori, atunci orice set de variabile necesare în același timp pot fi stocate în cel mult ''k'' registre.

=== Alte aplicații ===
Problema colorării grafurilor apare în mai multe domenii practice, cum ar fi potrivirea șabloanelor, planificarea evenimentelor sportive, proiectarea locurilor unor persoane la evenimente, orarele de examen, programarea taxiurilor, și rezolvarea puzzle-urilor [[Sudoku]].<ref name="Lewis2015">Lewis, R. ''A Guide to Graph Colouring: Algorithms and Applications''. Springer International Publishers, 2015.</ref>

== Alte colorări ==

=== Teoria lui Ramsey ===
O clasă importantă de probleme de colorare ''improprii'' este studiată în [[teoria lui Ramsey]], unde muchiilor grafului i se atribuie culori, și nu există nicio restricție cu privire la culorile de muchiilor incidente. Un exemplu simplu este teorema prieteniei, care prevede că în orice colorare a muchiilor lui <math>K_6</math>, graful complet cu șase noduri, va exista un triunghi monocromatic; de multe ori ilustrată prin a spune că orice grup de șase oameni, fie are trei persoane care nu se cunosc, fie are trei cunoștințe comune. Teoria lui Ramsey se ocupă cu generalizări ale acestei idei pentru a căuta regularitate în dezordine, găsind condiții generale pentru existența subgrafurilor monocromatice cu o structură dată.

== Notes ==
<references responsive />

== Bibliografie ==
{{refbegin|2}}
* {{Citation
 | last1=Barenboim | first1=L.
 | last2=Elkin | first2=M.
 | contribution=Distributed (Δ&nbsp;+&nbsp;1)-coloring in linear (in Δ) time
 | pages=111–120
 | title=Proceedings of the 41st {{Ill-wd|Q7661893}}
 | year=2009
 | doi=10.1145/1536414.1536432
 | isbn=978-1-60558-506-2
}}
* {{Citation
 | last1=Panconesi | first1=A.
 | last2=Srinivasan | first2=A.
 | contribution=On the complexity of distributed network decomposition
 | title=Journal of Algorithms
 | volume= 20
 | year=1996
}}
* {{Citation
 | last1=Schneider
 | first1=J.
 | contribution=A new technique for distributed symmetry breaking
 | title=Proceedings of the {{Ill-wd|Q7661889}}
 | year=2010
 | contribution-url=http://www.dcg.ethz.ch/publications/podcfp107_schneider_188.pdf
 | access-date=2017-06-20
 | archive-date=2013-07-30
 | archive-url=https://web.archive.org/web/20130730041102/http://dcg.ethz.ch/publications/podcfp107_schneider_188.pdf
 | dead-url=yes
 }}
* {{Citation
 | last1=Schneider
 | first1=J.
 | contribution=A log-star distributed maximal independent set algorithm for growth-bounded graphs
 | title=Proceedings of the {{Ill-wd|Q7661889}}
 | year=2008
 | contribution-url=http://www.dcg.ethz.ch/publications/podc08SW.pdf
 | access-date=2017-06-20
 | archive-date=2013-07-30
 | archive-url=https://web.archive.org/web/20130730030336/http://dcg.ethz.ch/publications/podc08SW.pdf
 | dead-url=yes
 }}
* {{Citation
| last1= Beigel | first1= R.
| last2= Eppstein | first2= D. | authorlink2= David Eppstein
|title=  3-coloring in time O(1.3289<sup>n</sup>)
|journal= [[Elsevier]]
|volume= 54
|pages=168–204
|year=2005 | issue= 2)
| doi= 10.1016/j.jalgor.2004.06.008
}}
* {{Citation
 | last1=Björklund | first1=A.
 | last2=Husfeldt | first2=T.
 | last3=Koivisto | first3=M.
 | journal={{Ill-wd|Q7390263}}
 | pages=546–563
 | title=Set partitioning via inclusion–exclusion
 | volume= 39
 | year=2009
 | doi=10.1137/070683933| issue=2
}}
* {{Citation
 | last = Brélaz | first = D. | authorlink = Daniel Brélaz
 | title = New methods to color the vertices of a graph
 | journal = {{Ill-wd|Q1120519}}
 | volume = 22
 | year = 1979
 | pages = 251–256
 | doi = 10.1145/359094.359101
 | issue = 4
}}
* {{Citation
 | last = Brooks | first = R. L.
 | last2 = Tutte
 | first2 = W. T.
 | title = On colouring the nodes of a network
 | journal = {{Ill-wd|Q6786838}}
 | volume = 37
 | year = 1941
 | pages = 194–197
 | doi = 10.1017/S030500410002168X
 | issue = 2
}}
* {{Citation
 | last1 = de Bruijn
 | first1 = N. G.
 | authorlink1 = Nicolaas Govert de Bruijn
 | last2 = Erdős
 | first2 = P.
 | authorlink2 = Paul Erdős
 | title = A colour problem for infinite graphs and a problem in the theory of relations
 | journal = Nederl. Akad. Wetensch. Proc. Ser. A
 | volume = 54
 | year = 1951
 | pages = 371–373
 | url = http://www.math-inst.hu/~p_erdos/1951-01.pdf
 }} (= ''Indag. Math.'' '''13''')
* {{Citation
|last=Byskov|first=J.M.
|title=Enumerating maximal independent sets with applications to graph colouring
|journal=[[Operations Research Letters]]
|pages=547–556
|volume=32
|year= 2004
|doi=10.1016/j.orl.2004.03.002
|issue=6
}}

* {{Citation
 | last = Chaitin | first = G. J.
 | contribution = Register allocation & spilling via graph colouring
 | title = Proc. 1982 {{Ill-wd|Q7248487}}
 | year = 1982
 | pages = 98–105
 | doi = 10.1145/800230.806984
 | isbn = 0-89791-074-5
}}
* {{Citation
 | last1 = Cole | first1 = R.
 | last2 = Vishkin | first2 = U.
 | year = 1986
 | title = Deterministic coin tossing with applications to optimal parallel list ranking
 | journal = {{Ill-wd|Q6030974}}
 | volume = 70
 | issue = 1
 | pages = 32–53
 | doi = 10.1016/S0019-9958(86)80023-7
}}
* {{Citation
 | last1 = Cormen | first1 = T. H.
 | last2 = Leiserson | first2 = C. E.
 | last3 = Rivest | first3 = R. L.
 | title = {{Ill-wd|Q1141518}}
 | publisher = The MIT Press
 | year = 1990
 | edition = 1st
}}
* {{Citation
 | last1 = Dailey | first1 = D. P.
 | title = Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
 | journal = {{Ill-wd|Q5282038|3=Discrete Mathematics}}
 | volume = 30
 | pages = 289–293
 | year = 1980
 | doi = 10.1016/0012-365X(80)90236-8
 | issue = 3
}}
* {{Citation
| last1=Duffy
| first1=K.
| last2=O'Connell
| first2=N.
| last3=Sapozhnikov
| first3=A.
| title=Complexity analysis of a decentralised graph colouring algorithm
| journal=Information Processing Letters
| volume=107
| pages=60–63
| year=2008
| url=http://www.hamilton.ie/ken_duffy/Downloads/cfl.pdf
| doi=10.1016/j.ipl.2008.01.002
| issue=2
}}
* {{Citation
 | last1 = Fawcett | first1 = B. W.
 | title = On infinite full colourings of graphs
 | journal = {{Ill-wd|Q2780987|3=Can. J. Math.}}
 | volume = 30
 | pages = 455–457
 | year = 1978
 | doi =10.4153/cjm-1978-039-8
}}

* {{Citation
 | last1 = Fomin | first1 = F.V.
 | last2 = Gaspers | first2 = S.
 | last3 = Saurabh | first3 = S.
 | contribution = Improved Exact Algorithms for Counting 3- and 4-Colorings
 | title = Proc. 13th Annual International Conference, COCOON 2007
 | series = {{Ill-wd|Q924044}}
 | volume = 4598
 | publisher = Springer
 | year = 2007
 | pages = 65–74
 | doi = 10.1007/978-3-540-73545-8_9
 | isbn=978-3-540-73544-1
}}
* {{Citation
 | last1 = Garey | first1 = M. R. | authorlink1 = Michael R. Garey
 | last2 = Johnson | first2 = D. S. | authorlink2 = David S. Johnson
 | year = 1979
 | title = {{Ill-wd|Q938821}}
 | publisher = W.H. Freeman
 | isbn = 0-7167-1045-5
}}
* {{Citation
 | last1 = Garey
 | first1 = M. R.
 | authorlink1 = Michael R. Garey
 | last2 = Johnson
 | first2 = D. S.
 | authorlink2 = David S. Johnson
 | last3 = Stockmeyer
 | first3 = L.
 | authorlink3 = Larry Stockmeyer
 | year = 1974
 | contribution = Some simplified NP-complete problems
 | url = http://portal.acm.org/citation.cfm?id=803884
 | title = Proceedings of the Sixth Annual ACM Symposium on Theory of Computing
 | pages = 47–63
 | doi = 10.1145/800119.803884
 }}
* {{Citation
 | last1 = Goldberg | first1 = L. A. | author1-link = Leslie Ann Goldberg
 | last2 = Jerrum | first2 = M. | authorlink2 = Mark Jerrum
 | title = Inapproximability of the Tutte polynomial
 | journal = {{Ill-wd|Q6030974}}
 | volume = 206
 |  issue= 7
| date= July 2008
 | pages = 908–929
 | doi = 10.1016/j.ic.2008.04.003
}}
* {{Citation
 | last1 = Goldberg | first1 = A. V. | author1-link = Andrew V. Goldberg
 | last2 = Plotkin | first2 = S. A.
 | last3 = Shannon | first3 = G. E.
 | year = 1988
 | title = Parallel symmetry-breaking in sparse graphs
 | journal = {{Ill-wd|Q7390256}}
 | volume = 1
 | issue = 4
 | pages = 434–446
 | doi = 10.1137/0401044
}}
* {{Citation
 | last1 = Guruswami | first1 = V.
 | last2 = Khanna | first2 = S.
 | contribution = On the hardness of 4-coloring a 3-colorable graph
 | title = Proceedings of the 15th Annual IEEE Conference on Computational Complexity
 | pages = 188–197
 | year = 2000
 | doi = 10.1109/CCC.2000.856749
 | isbn = 0-7695-0674-7
}}
* {{Citation
 | last = Halldórsson | first = M. M.
 | year = 1993
 | title = A still better performance guarantee for approximate graph coloring
 | journal = Information Processing Letters
 | volume = 45
 | pages = 19–23
 | doi = 10.1016/0020-0190(93)90246-6
}}
* {{Citation
 | last = Holyer | first = I.
 | year = 1981
 | title = The NP-completeness of edge-coloring
 | journal = {{Ill-wd|Q7390263}}
 | volume = 10
 | pages = 718–720
 | doi = 10.1137/0210055
 | issue = 4
}}
* {{Citation
 | last1 = Crescenzi | first1 = P.
 | last2 = Kann | first2 = V.
 | title = How to find the best approximation results — a follow-up to Garey and Johnson
 | journal = {{Ill-wd|Q3387984}}
 | date = December 1998
 | doi = 10.1145/306198.306210
 | volume = 29
 | page = 90
 | issue = 4
}}
* {{Citation
 | last1 = Jaeger | first1 = F.
 | last2 = Vertigan | first2 = D. L.
 | last3 = Welsh | first3 = D. J. A.
 | year = 1990
 | title = On the computational complexity of the Jones and Tutte polynomials
 | journal = {{Ill-wd|Q6786838}}
 | volume = 108
 | pages = 35–53
 | doi = 10.1017/S0305004100068936
}}
* {{Citation
 | last1 = Jensen | first1 = T. R.
 | last2 = Toft | first2 = B.
 | title = Graph Coloring Problems
 | publisher = Wiley-Interscience, New York
 | year = 1995
 | isbn = 0-471-02865-7
}}
* {{Citation
 | last = Khot | first = S. |authorlink = Subhash Khot | year = 2001
 | contribution = Improved inapproximability results for MaxClique, chromatic number and approximate graph coloring
 | title = Proc. 42nd Annual {{Ill-wd|Q7661883}}
 | pages = 600–609
 | doi = 10.1109/SFCS.2001.959936
 | isbn = 0-7695-1116-3
}}
* {{Citation
 | last1 = Kubale | first1 = M.
 | title = Graph Colorings
 | publisher = [[American Mathematical Society]]
 | year = 2004
 | isbn = 0-8218-3458-4
}}
* {{Citation
 | last1=Kuhn | first1=F.
 | contribution=Weak graph colorings: distributed algorithms and applications
 | pages=138–144
 | title=Proceedings of the 21st {{Ill-wd|Q7661887}}
 | year=2009
 | doi=10.1145/1583991.1584032
 | isbn=978-1-60558-606-9
}}
* {{Citation
 | last1=Lawler | first1=E.L. | authorlink = Eugene Lawler
 | title=A note on the complexity of the chromatic number problem
 | pages=66–67
 | journal={{Ill-wd|Q129239}}
 | year=1976
|volume= 5
 | doi=10.1016/0020-0190(76)90065-X| issue=3
}}
* {{Citation
 | last1 = Leith
 | first1 = D.J.
 | last2 = Clifford
 | first2 = P.
 | year = 2006
 | contribution = A Self-Managed Distributed Channel Selection Algorithm for WLAN
 | title = Proc. RAWNET 2006, Boston, MA
 | url = http://www.hamilton.ie/peterc/downloads/rawnet06.pdf
 | accessdate = 2016-03-03
 }}
* {{Citation
 | last1 = Linial | first1 = N. | authorlink = Nati Linial
 | year = 1992
 | title = Locality in distributed graph algorithms
 | journal = {{Ill-wd|Q7390263}}
 | volume = 21
 | issue = 1
 | pages = 193–201
 | doi = 10.1137/0221015
}}
* {{Citation
 | last1 = van Lint| first1 = J. H.
 | last2 = Wilson | first2 = R. M.
 | title = A Course in Combinatorics
 | year = 2001
 | edition = 2nd
 | publisher = Cambridge University Press
 | isbn = 0-521-80340-3
}}
* {{Citation
 | last = Marx | first = Dániel
 | contribution = Graph colouring problems and their applications in scheduling
 | title = Periodica Polytechnica, Electrical Engineering
 | year = 2004
 | pages = 11–16
 | volume = 48
 |issue=1–2
 | citeseerx = 10.1.1.95.4268
}}
*{{citation
 | last = Mycielski
 | first = J.
 | author-link = Jan Mycielski
 | journal = Colloq. Math.
 | pages = 161–162
 | title = Sur le coloriage des graphes
 | url = http://matwbn.icm.edu.pl/ksiazki/cm/cm3/cm3119.pdf
 | volume = 3
 | year = 1955
 }}.
*{{citation
 | last1 = Nešetřil | first1 = Jaroslav | author1-link = Jaroslav Nešetřil
 | last2 = Ossona de Mendez | first2 = Patrice | author2-link = Patrice Ossona de Mendez
 | contribution = Theorem 3.13
 | doi = 10.1007/978-3-642-27875-4
 | isbn = 978-3-642-27874-7
 | location = Heidelberg
 | mr = 2920058
 | page = 42
 | publisher = Springer
 | series = Algorithms and Combinatorics
 | title = Sparsity: Graphs, Structures, and Algorithms
 | volume = 28
 | year = 2012}}.
*{{Citation
 | last1=Panconesi
 | first1=Alessandro
 | last2=Rizzi
 | first2=Romeo
 | title=Some simple distributed algorithms for sparse networks
 | publisher=[[Springer Science+Business Media]]
 | location=Berlin, New York
 | year=2001
 | journal=Distributed Computing
 | issn=0178-2770
 | volume=14
 | issue=2
 | pages=97–100
 | doi=10.1007/PL00008932
}}
* {{Citation
 | last1 = Sekine | first1 = K.
 | last2 = Imai | first2 = H.
 | last3 = Tani | first3 = S.
 | contribution = Computing the Tutte polynomial of a graph of moderate size
 | title = Proc. 6th International Symposium on Algorithms and Computation (ISAAC 1995)
 | series = {{Ill-wd|Q924044}}
 | volume = 1004
 | publisher = Springer
 | year = 1995
 | pages = 224–233
 | doi = 10.1007/BFb0015427
 | isbn = 3-540-60573-8
}}
* {{Citation
 | last1 = Welsh | first1 = D. J. A.
 | last2 = Powell | first2 = M. B.
 | year = 1967
 | title = An upper bound for the chromatic number of a graph and its application to timetabling problems
 | journal = The Computer Journal
 | volume = 10
 | doi = 10.1093/comjnl/10.1.85
 | pages = 85–86
 | issue= 1
}}
* {{Citation
 | last = West
 | first = D. B.
 | title = Introduction to Graph Theory
 | year = 1996
 | publisher = Prentice-Hall
 | isbn = 0-13-227828-6
}}
* {{Citation
 | last = Wilf | first = H. S.
 | title = Algorithms and Complexity
 | publisher = Prentice–Hall
 | year = 1986
}}
* {{Citation
 | last = Zuckerman | first = D.
 | title = Linear degree extractors and the inapproximability of Max Clique and Chromatic Number
 | journal = {{Ill-wd|Q7782416|3=Theory of Computing}}
 | volume = 3
 | pages = 103–128
 | year = 2007
 | doi = 10.4086/toc.2007.v003a006
}}
* {{Citation
 |last     = Zykov
 |first    = A. A.
 |title    = О некоторых свойствах линейных комплексов (On some properties of linear complexes)
 |language = Russian
 |journal  = Math. Sbornik.
 |volume   = 24(66)
 |issue    = 2
 |year     = 1949
 |pages    = 163–188
 |url      = http://mi.mathnet.ru/eng/msb5974
}}
* {{Citation
 | last1 = Jensen | first1 = Tommy R.
 | last2 = Toft   | first2 = Bjarne
 | title = Graph Coloring Problems
 | isbn = 9780471028659
 | publisher = John Wiley & Sons
 | year = 1995
}}
{{refend}}

== Legături externe ==
* [https://webdocs.cs.ualberta.ca/~joe/Coloring/index.html ''Pagină de colorare a grafurilor''] {{Webarchive|url=https://web.archive.org/web/20160922203225/http://webdocs.cs.ualberta.ca/~joe/Coloring/index.html |date=2016-09-22 }} de Joseph Culberson (programe de colorare a grafurilor)
* [http://rhydlewis.eu/resources/gCol.zip ''High-Performance Graph Colouring Algorithms''] Suită de 8 algoritmi diferiți (implementați în C++) de Rhyd Lewis
* [http://vispo.com/software ''CoLoRaTiOn''] de Jim Andrews și Mike Fellows este un puzzle de colorare a grafurilor
* [http://www.adaptivebox.net/research/bookmark/gcpcodes_link.html Legături către coduri sursă de colorarea grafurilor] {{Webarchive|url=https://web.archive.org/web/20080704082406/http://www.adaptivebox.net/research/bookmark/gcpcodes_link.html |date=2008-07-04 }}
* [http://www.mcs.vuw.ac.nz/~djp/tutte/ Cod pentru calculul eficient al polinoamelor Tutte, cromatic și de flux] {{Webarchive|url=https://web.archive.org/web/20080416050948/http://www.mcs.vuw.ac.nz/~djp/tutte/ |date=2008-04-16 }} de Gary Haggard, David J. Pearce și Gordon Royle
* [http://graph-coloring.appspot.com/ O aplicație web de colorare a grafurilor] {{Webarchive|url=https://web.archive.org/web/20120622103928/http://graph-coloring.appspot.com/ |date=2012-06-22 }} de Jose Antonio Martin H.
[[Categorie:Probleme NP-complete]]
[[Categorie:Probleme NP-hard]]
[[Categorie:Teoria grafurilor]]