Colorarea graficelor

O colorare exactă a vârfurilor grafului Petersen cu 3 culori, numărul minim posibil.

În teoria graficelor , colorarea graficelor este un caz special de etichetare a graficelor ; este o atribuire de etichete, denumite în mod tradițional „culori”, elementelor unui grafic supuse anumitor constrângeri. În forma sa cea mai simplă, este un mod de a colora vârfurile unui grafic astfel încât niciunul dintre cele două vârfuri adiacente să nu aibă aceeași culoare; aceasta se numește colorare vertex . În mod similar, o colorare a marginilor atribuie o culoare fiecărei margini, astfel încât niciuna dintre cele două margini adiacente nu împarte aceeași culoare, iar o colorare a fețelor unui grafic plan nu atribuie o culoare fiecărei fețe sau regiuni în așa fel încât nici fața care are un chenar are aceeași culoare.

Colorarea vertexului este punctul de plecare al argumentului, iar alte probleme de colorare pot fi transformate într-o versiune vertex. De exemplu, o colorare a marginilor unui grafic este doar o colorare a vârfurilor unui grafic liniar , iar o colorare a fețelor unui grafic plan este doar o colorare a vârfurilor dualului său. Cu toate acestea, problemele de colorare a vârfurilor sunt adesea menționate și studiate așa cum sunt . Acest lucru este parțial pentru perspectivă și parțial pentru că unele probleme sunt cel mai bine studiate în alte forme decât vârfuri, cum ar fi colorarea marginilor.

Convenția utilizării culorilor provine din colorarea țărilor de pe o hartă, unde fiecare față este literalmente colorată. Acest lucru a fost apoi generalizat la colorarea fețelor unui grafic încorporat în plan. Datorită dualității planare, am trecut la colorarea vârfurilor și, în această formă, generalizăm la toate graficele. În reprezentările matematice și computerizate, este tipic să se utilizeze primele numere întregi pozitive sau non-negative ca „culori”. În general, orice set finit poate fi folosit ca „set de culori”. Natura problemei de colorare depinde de numărul de culori, dar nu de ceea ce sunt.

Colorarea graficelor se bucură de multe aplicații practice, precum și de multe provocări teoretice. În plus față de problemele clasice, pot fi plasate și diferite limitări pe grafic, sau pe modul în care este atribuită o culoare, sau chiar pe culoare în sine. Subiectul a câștigat popularitate și în rândul publicului larg sub forma popularului puzzle Sudoku . Colorarea graficelor este încă un domeniu de cercetare foarte activ.

Notă: Mulți termeni folosiți în acest articol sunt definiți în Glosarul teoriei graficelor .

Istorie

Același subiect în detaliu: Teorema celor patru culori și Teoria graficelor .

Primele rezultate privind colorarea graficelor se referă aproape exclusiv la graficele plane sub forma colorării hărților . În timp ce încerca să coloreze o hartă a județelor Angliei, Francis Guthrie a postulat teorema celor patru culori , menționând că patru culori erau suficiente pentru a colora harta, astfel încât nicio regiune care are o frontieră comună să nu primească aceeași culoare. Fratele lui Guthrie i-a transmis problema profesorului său de matematică Augustus de Morgan de la University College , care a menționat-o într-o scrisoare adresată lui William Hamilton în 1852. Arthur Cayley a ridicat problema la o reuniune a Societății de Matematică din Londra în 1879. În același an, Alfred Kempe a publicat un eseu susținând că a stabilit rezultatul, iar timp de un deceniu problema celor patru culori a fost considerată rezolvată. Pentru isprava sa, Kempe a fost ales membru al Royal Society și mai târziu președinte al London Mathematical Society. ^[1]

În 1890, Heawood a subliniat că argumentul lui Kempe era greșit. Cu toate acestea, în eseul respectiv a demonstrat teorema celor cinci culori , spunând că orice hartă plană poate fi colorată cu cel mult cinci culori, folosind ideile lui Kempe. În secolul următor, s-au dezvoltat o mare cantitate de muncă și teorii pentru a reduce numărul de culori la patru, până când teorema celor patru culori a fost definitiv demonstrată în 1976 de Kenneth Appel și Wolfgang Haken . Dovada s-a întors la ideile lui Heawood și Kempe și a ignorat în mare măsură evoluțiile care avuseseră loc. ^[2] Dovada teoremei celor patru culori se remarcă și prin faptul că este prima dovadă majoră asistată de computer.

În 1912, George David Birkhoff a introdus polinomul cromatic pentru a studia problemele colorării, care a fost apoi generalizată de Tutti la polinomul Tutti , o structură importantă în teoria algebrică a graficelor. Kemoe a atras deja atenția asupra cazului general, non-plan, în 1879 ^[3], și multe rezultate privind generalizările graficelor plane colorate pe suprafețe de ordin superior urmate la începutul secolului al XX-lea.

În 1960, Claude Berge a formulat o altă presupunere despre colorarea graficului, supoziția grafică perfectă puternică , motivată inițial de un concept al teoriei informației numit capacitatea de eroare zero a unui grafic, introdus de Shannon . Conjectura a rămas nerezolvată timp de 40 de ani, până când în 2002 a fost enunțată ca celebră teoremă a graficului perfect perfect de către Chudnovsky , Robertson , Seymour și Thomas .

Colorarea graficului a fost studiată ca o problemă algoritmică încă de la începutul anilor 1970: problema numărului cromatic este una dintre cele 21 probleme complete ale NP ale lui Karp din 1972 și, în același timp, au fost dezvoltați diferiți algoritmi de timp exponențiali pe bază de căi înapoi ( backtracking ) și asupra recidivei de contracție-anulare a lui Zykov (1949) . Una dintre principalele aplicații de colorare a graficelor, alocarea registrelor în compilatoare, a fost introdusă în 1981.

Definiție și terminologie

Acest grafic poate fi tri-colorat în 12 moduri diferite.

Colorare vertex

Când este utilizată fără nicio specificație, colorarea unui grafic este aproape întotdeauna o colorare exactă a vârfurilor , adică o etichetare a vârfurilor graficului cu culori astfel încât nicio pereche de vârfuri care au aceeași margine să nu aibă aceeași culoare. Deoarece un vârf cu o buclă nu ar putea fi niciodată colorat exact, se înțelege că graficele din acest context sunt fără o buclă.

Terminologia utilizării culorilor pentru etichetele vertexului revine la colorarea hărților. Etichete precum roșu și albastru sunt utilizate numai atunci când numărul de culori este mic și, de obicei, vrem să spunem că etichetele sunt trase din numărul întreg {1,2,3, ...}.

O colorare care folosește cel mult k culori se numește colorare k (corect). Numărul minim de culori necesar pentru colorarea unui grafic G se numește numărul său cromatic și este adesea notat χ ( G ). Uneori se folosește γ ( G ), deoarece χ ( G ) este folosit și pentru caracteristica Euler a unui grafic. Un grafic căruia i se poate atribui k- colorare (exactă) este k- colorare și este k- cromatic dacă numărul său cromatic este exact k . Un subset de vârfuri atribuite aceleiași culori se numește clasă de culoare , fiecare clasă de acest tip formând unset independent . Astfel, o colorare k este aceeași cu o partiție a setului de vârfuri în k seturi independente, iar termenii k-party și k-colorable au aceeași semnificație.

Polinom cromatic

Același subiect în detaliu: Polinom cromatic .

Polinomul cromatic contează numărul de moduri în care un grafic poate fi colorat folosind nu mai mult de un număr dat de culori. De exemplu, folosind trei culori, graficul din imaginea din dreapta poate fi colorat l în 12 moduri. Cu doar două culori, nu poate fi deloc colorată. Cu patru culori, poate fi colorată în 24 + 4⋅12 = 72 de moduri: folosind toate cele patru culori, există 4! = 24 de culori valide ( fiecare atribuire a patru culori la orice grafic pe 4 vârfuri este o culoare exactă); și pentru fiecare alegere dintre trei dintre cele patru culori, există 12 culori valide cu 3 culori. Deci, pentru graficul de exemplu, un tabel cu numărul de culori valide ar începe astfel:

Culori disponibile	1	2	3	4	...
Număr de culori	0	0	12	72	...

Polinomul cromatic este o funcție P ( G , t ) care numără numărul de t- culori ale lui G. După cum indică și numele, pentru un G dat funcția este de fapt un polinom în t . Pentru graficul exemplului, P ( G , t ) = t ( t - 1) ² ( t - 2) și, de fapt, P ( G , 4) = 72.

Polinomul cromatic include cel puțin la fel de multe informații despre colorabilitatea lui G a numărului cromatic. De fapt, χ este cel mai mic întreg pozitiv care nu este o rădăcină a polinomului cromatic

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

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

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

Polinoame cromatice pentru anumite grafice
Triunghiul K ₃	$t(t-1)(t-2)$ ${\ displaystyle t (t-1) (t-2)}$ $t (t-1) (t-2)$
Completați graficul K _n	$t(t-1)(t-2)\cdots (t-(n-1))$ ${\ displaystyle t (t-1) (t-2) \ cdots (t- (n-1))}$ $t (t-1) (t-2) \ cdots (t- (n-1))$
Arborele cu n vârfuri	$t(t-1)^{n-1}$ ${\ displaystyle t (t-1) ^ {n-1}}$ $t (t-1) ^ {{n-1}}$
Ciclul C _n	$(t-1)^{n}+(-1)^{n}(t-1)$ ${\ displaystyle (t-1) ^ {n} + (- 1) ^ {n} (t-1)}$ $(t-1) ^ {n} + (- 1) ^ {n} (t-1)$
Graficul Petersen	$t(t-1)(t-2)(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t-352)$ ${\ displaystyle t (t-1) (t-2) (t ^ {7} -12t ^ {6} + 67t ^ {5} -230t ^ {4} + 529t ^ {3} -814t ^ {2} + 775t-352)}$ $t (t-1) (t-2) (t ^ {7} -12t ^ {6} + 67t ^ {5} -230t ^ {4} + 529t ^ {3} -814t ^ {2} + 775t- 352)$

Colorarea muchiilor

Același subiect în detaliu: Colorarea marginilor .

O colorare a marginilor unui grafic este o colorare exactă a marginilor , ceea ce înseamnă o atribuire de culori marginilor, astfel încât niciun vârf să nu fie incident la două margini de aceeași culoare. O colorare a muchiilor cu k culori se numește colorare a marginii k și este echivalentă cu problema împărțirii setului de margini în k mates . Cel mai mic număr de culori necesare pentru colorarea marginilor unui grafic G este indicele cromatic sau numărul cromatic de margini , χ ′ (G) . O colorare Tait este o 3-colorare a marginilor unui grafic cub . Teorema celor patru culori este echivalentă cu afirmația că fiecare grafic cub planar fără punți admite o colorare Tait.

Colorare totală

Același subiect în detaliu: Colorare totală .

Colorarea totală este un tip de colorare pe vârfurile și marginile unui grafic. Când se folosește fără nicio specificație, o colorare totală este întotdeauna presupusă a fi exactă, ceea ce înseamnă că niciun vârf adiacent, nici o margine adiacentă și nici o margine și vârfuri extreme nu au aceeași culoare. Numărul cromatic total χ ″ (G) al unui grafic G este numărul minim de culori necesar pentru orice colorare totală a lui G.

Proprietate

Limite la numărul cromatic

Atribuirea culorilor distincte vârfurilor distincte produce întotdeauna și o colorare exactă

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

{\ displaystyle 1 \ leq \ chi (G) \ leq n. \,}

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

Singurele grafice care pot fi 1-colorate sunt graficele fără punte . Un grafic complet $K_{n}$ ${\ displaystyle K_ {n}}$ $K_ {n}$ de n vârfuri necesită $\chi (K_{n})=n$ ${\ displaystyle \ chi (K_ {n}) = n}$ $\ chi (K_ {n}) = n$ culori. În colorarea optimă trebuie să existe cel puțin una dintre marginile m ale graficului între fiecare pereche de clase de culori, deci

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

{\ displaystyle \ chi (G) (\ chi (G) -1) \ leq 2m. \,}

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

Dacă G conține o fisură de dimensiunea k , atunci sunt necesare cel puțin k culori pentru a colora acea fisură; cu alte cuvinte, numărul cromatic este cel puțin numărul fisurii:

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

{\ displaystyle \ chi (G) \ geq \ omega (G). \,}

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

Pentru graficele de intervale această limită este strânsă.

Graficele bicolorabile sunt exact grafice bipartite , care includ copaci și păduri. Prin teorema celor patru culori, orice grafic plan poate fi de 4 culori.

O colorare lacomă arată că fiecare grafic poate fi colorat cu o culoare mai mult decât gradul maxim al vârfurilor,

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

{\ displaystyle \ chi (G) \ leq \ Delta (G) +1. \,}

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

Graficele complete au $\chi (G)=n$ ${\ displaystyle \ chi (G) = n}$ $\ chi (G) = n$ Și $\Delta (G)=n-1$ ${\ displaystyle \ Delta (G) = n-1}$ $\ Delta (G) = n-1$ , iar ciclurile ciudate au $\chi (G)=3$ ${\ displaystyle \ chi (G) = 3}$ $\ chi (G) = 3$ Și $\Delta (G)=2$ ${\ displaystyle \ Delta (G) = 2}$ $\ Delta (G) = 2$ , deci pentru aceste grafice această limită este cea mai bună posibilă. În toate celelalte cazuri, limita poate fi ușor îmbunătățită; Teorema lui Brooks ^[4] afirmă că

Teorema lui Brooks:

\chi (G)\leq \Delta (G)

{\ displaystyle \ chi (G) \ leq \ Delta (G)}

\ chi (G) \ leq \ Delta (G)

pentru un grafic conectat, G simplu, cu excepția cazului în care G este un grafic complet sau un ciclu impar.

Grafice cu număr cromatic ridicat

Graficele cu fisuri mari au un număr cromatic ridicat, dar inversul nu este adevărat. Graficul Grötzsch este un exemplu de grafic 4-cromatic fără triunghi, iar exemplul poate fi generalizat la graficele Mycielski .

Teorema lui Mycielski ( Zykov (1949) , Mycielski (1955) ): există grafice fără triunghiuri cu numere cromatice arbitrar mari.

Prin teorema lui Brooks, graficele cu un număr cromatic ridicat trebuie să aibă cel mai înalt grad. O altă proprietate locală care duce la un număr cromatic ridicat este prezența unei clici mari. Dar colorabilitatea nu este un fenomen cu totul local: un grafic cu un calibru ridicat seamănă local cu un copac, deoarece toate ciclurile sunt lungi, dar numărul său cromatic nu trebuie să fie 2:

Teorema (Erdős): există grafice de calibru arbitrar ridicat și număr cromatic.

Limite la indicele cromatic

Un colorat de vârf al lui G este un colorat de vârf al graficului său liniar $L(G)$ ${\ displaystyle L (G)}$ $L (G)$ , si invers. Asa,

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

{\ displaystyle \ chi '(G) = \ chi (L (G)). \,}

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

Există o relație puternică între colorabilitatea marginilor și gradul maxim al graficului $\Delta (G)$ ${\ displaystyle \ Delta (G)}$ $\ Delta (G)$ . Întrucât toate muchiile incidente pe același vârf au nevoie de propria lor culoare, avem

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

{\ displaystyle \ chi '(G) \ geq \ Delta (G). \,}

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

În plus,

Teorema lui König :

\chi '(G)=\Delta (G)

{\ displaystyle \ chi '(G) = \ Delta (G)}

\ chi '(G) = \ Delta (G)

dacă G este bipartit.

În general, relația este chiar mai puternică decât cea pe care o oferă teorema lui Brooks pentru colorarea vertexului:

Teorema lui Vizing: un grafic al gradului maxim

\Delta

{\ displaystyle \ Delta}

\ Delta

are număr cromatic de margini

\Delta

{\ displaystyle \ Delta}

\ Delta

sau

\Delta +1

{\ displaystyle \ Delta +1}

\ Delta +1

.

Alte proprietăți

Un grafic are o culoare k- dacă și numai dacă are o orientare aciclică pentru care cea mai lungă cale are cel mult lungimea k ; aceasta este teorema Gallai-Hasse-Roy-Vitaver ( Nešetřil & Ossona de Mendez (2012) ).

Pentru graficele plane, colorațiile vertexului sunt în esență duale pentru fluxurile zero nicăieri .

Despre grafurile infinite, se știe mult mai puțin. Iată două dintre puținele rezultate privind colorarea graficelor infinite:

Dacă toate subgrafele finite ale unui grafic infinit G sunt k- colorabile, atunci la fel este și G , pe baza presupunerii axiomei de alegere . Aceasta este teorema lui Bruijn - Erdős ( de Bruijn & Erdős (1951) ).
Dacă un grafic admite o n- colorare completă pentru fiecare n ≥ n ₀ , admite o colorare infinită completă (Fawcett (1978) .

Probleme deschise

Numărul cromatic al planului , unde două puncte sunt adiacente dacă au distanță unitară, este necunoscut, deși este unul dintre 4, 5, 6 sau 7. Alte probleme deschise referitoare la numărul cromatic al graficelor includ conjectura lui Hadwiger care afirmă că fiecare graficul cu număr cromatic k are un grafic complet pe k vârfuri ca minore , conjectura Erdős - Faber - Lovász care limitează numărul cromatic de uniuni ale graficelor complete care au exact un vârf în comun pentru fiecare pereche și conjectura Albertson conform căreia din graficele k- cromatice graficele complete sunt cele cu cel mai mic număr de traversări .

Când Birkhoff și Lewis au introdus polinomul cromatic în atacul lor asupra teoremei celor patru culori, au conjecturat că pentru graficele plane G , polinomul $P(G,t)$ ${\ displaystyle P (G, t)}$ $P (G, t)$ nu are zerouri în regiune $[4,\infty )$ ${\ displaystyle [4, \ infty)}$ $[4, \ infty)$ . Deși se știe că acest polinom cromatic nu are zerouri în regiune $[5,\infty )$ ${\ displaystyle [5, \ infty)}$ $[5, \ infty)$ este asta $P(G,4)\neq 0$ ${\ displaystyle P (G, 4) \ neq 0}$ $P (G, 4) \ neq 0$ , conjectura lor este încă nerezolvată. Rămâne, de asemenea, o problemă nerezolvată pentru caracterizarea graficelor care au același polinom cromatic și pentru determinarea care polinomii sunt cromatici.

Algoritmi

Colorarea graficelor
Decizie
Nume	Colorarea graficului, colorarea k-
Intrare	Graficul G cu n vârfuri. k întreg
Ieșire	Admite G colorarea exactă a vârfurilor cu k culori?
Timpul de execuție	O (2 ⁿ n ) ^[5]
Complexitate	NP-complet
Reducere de la	3-satisfacție
Garey - Johnson	GT4
Optimizare
Nume	Număr cromatic
Intrare	Graficul G cu n vârfuri
Ieșire	χ ( G )
Complexitate	NP-dificil
Aproximabilitate	O ( n (log n ) ⁻³ (log log n ) ² )
Inaproximabilitate	O ( n ^{1 - ε} ) cu excepția cazului în care P = NP
Problemă de numărare
Nume	Polinom cromatic
Intrare	Graficul G cu n vârfuri. k întreg
Ieșire	Numărul P ( G , k ) de k- culori exacte ale lui G.
Timpul de execuție	O (2 ⁿ n )
Complexitate	# P-complet
Aproximabilitate	FPRAS pentru cazuri restricționate
Inaproximabilitate	Fără PTAS, cu excepția cazului în care P = NP

Timp polinomial

Determinarea dacă un grafic poate fi colorat cu 2 culori este echivalentă cu determinarea dacă graficul este sau nu bipartit și, prin urmare, calculabil în timp liniar folosind căutarea în amplitudine . Mai general, numărul cromatic și o colorare corespunzătoare a graficelor perfecte pot fi calculate în timp polinomial folosind programarea semidefinită . Formulele închise pentru polinomul cromatic sunt cunoscute pentru multe clase de grafice, cum ar fi pădurile, graficele corale, ciclurile, roțile și scale, deci acestea pot fi estimate în timp polinomial.

Dacă graficul este plan și are o lățime ramificată limitată (sau nu este plan, dar are o descompunere cunoscută a ramurilor), atunci poate fi rezolvat în timp polinomial folosind programarea dinamică. În general, timpul necesar este polinomial în dimensiunea graficelor, dar exponențial în lățimea ramurilor.

Algoritmi exacți

Metoda forței brute pentru o colorare k consideră fiecare dintre $k^{n}$ ${\ displaystyle k ^ {n}}$ $k ^ {n}$ atribuie k culori la n vârfuri și verifică pentru fiecare dacă este corect. Pentru a calcula numărul cromatic și polinomul cromatic, această procedură este utilizată pentru fiecare $k=1,\ldots ,n-1$ ${\ displaystyle k = 1, \ ldots, n-1}$ $k = 1, \ ldots, n-1$ , impracticabil pentru toate, cu excepția celor mai mici grafice primite.

Folosind programarea dinamică și o limită a numărului deseturi maxime independente , colorabilitatea k poate fi decisă în timp și spațiu $O(2,445^{n})$ ${\ displaystyle O (2.445 ^ {n})}$ $O (2.445 ^ {n})$ . ^[6] Folosind principiul includere-excludere și algoritmul Yates pentru transformarea rapidă zeta, colorabilitatea k poate fi dedusă în timp $O(2^{n}n)$ ${\ displaystyle O (2 ^ {n} n)}$ $O (2 ^ {n} n)$ ^[5] pentru orice k . Cei mai rapizi algoritmi sunt cunoscuți pentru 3 și 4 culori, care pot fi decise în timp $O(1,3289^{n})$ ${\ displaystyle O (1.3289 ^ {n})}$ $O (1.3289 ^ {n})$ ^[7] e $O(1,7272^{n})$ ${\ displaystyle O (1.7272 ^ {n})}$ $O (1.7272 ^ {n})$ , Respectiv ^[8] .

Contracție

Contracția $G/uv$ ${\ displaystyle G / uv}$ $G / uv$ a graficului G este graficul obținut prin identificarea vârfurilor u și v , îndepărtarea oricărei margini între ele și înlocuirea lor cu un singur vârf w unde orice margine care a fost incidentă pe u sau v este redirecționată către w . Această operație joacă un rol important în analiza colorării graficelor.

Numărul cromatic satisface relația de recurență :

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

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

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

datorită lui Zykov (1949) , unde u și v sunt vârfuri neadiacente, $G+uv$ ${\ displaystyle G + uv}$ $G + uv$ este graficul $tu v$ ${\ displaystyle uv}$ $uv$ adăugat. Mai mulți algoritmi se bazează pe estimarea acestei recurențe, arborele rezultat din calcul este uneori numit arborele Zykov. Timpul de execuție se bazează pe euristica pentru alegerea vârfurilor u și v .

Polinomul cromatic satisface următoarea relație de recurență

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

{\ displaystyle P (G-uv, k) = P (G / uv, k) + P (G, k)}

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

unde u și v vârfurile adiacente și $G-uv$ ${\ displaystyle G-uv}$ $G-uv$ este graficul cu muchia $tu v$ ${\ displaystyle uv}$ $uv$ îndepărtat. $P(G-uv,k)$ ${\ displaystyle P (G-uv, k)}$ $P (G-uv, k)$ reprezintă numărul de culori exacte posibile ale graficului, atunci când vârfurile pot avea aceleași culori sau culori diferite. Numărul de culori exacte provine, așadar, din suma a două grafice. Dacă vârfurile u și v au culori diferite, atunci putem lua în considerare și un grad, în care u și v sunt adiacente. Dacă u și v au aceleași culori, putem lua în considerare și un grafic, unde u și v sunt contractate. Curiozitatea tuturor celor ce alte proprietăți ale graficelor au îndeplinit acest eveniment l-a determinat să descopere o generalizare bivariantă a polinomului cromatic, polinomul tuturor .

Expresiile dau naștere unei proceduri recursive, numită algoritmul de anulare-contracție , care stă la baza multor algoritmi de colorare a graficelor. Timpul de execuție satisface aceeași relație de recurență ca secvența Fibonacci , deci, în cel mai rău caz, algoritmul rulează în timp într-un factor polinomial de $((1+{\sqrt {5}})/2)^{n+m}=O(1,6180^{n+m})$ ${\ displaystyle ((1 + {\ sqrt {5}}) / 2) ^ {n + m} = O (1.6180 ^ {n + m})}$ $((1 + {\ sqrt {5}}) / 2) ^ {{n + m}} = O (1.6180 ^ {{n + m}})$ pentru n vârfuri și m margini. ^[9] Analiza poate fi îmbunătățită în cadrul unui factor polinomial al numărului $t(G)$ ${\ displaystyle t (G)}$ $t (G)$ a copacilor care acoperă graficul de intrare. ^[10] În practică, strategiile de ramificare și legare și respingerea izomorfismului graficelor sunt utilizate pentru a evita unele apeluri recursive, iar timpul de execuție depinde de euristica utilizată pentru a capta perechea de vârfuri.

Colorare lacomă

Același subiect în detaliu: Colorarea lacomă .

Două culori lacome ale aceluiași grafic folosind ordine de vârf diferite. Exemplul din dreapta se generalizează în grafice bicolorabile cu n vârfuri, unde se petrece algoritmul lacom

n/2

{\ displaystyle n / 2}

n / 2

culori.

Algoritmul lacom consideră vârfurile într-o ordine specifică $v_{1}$ ${\ displaystyle v_ {1}}$ $v_1$ , ..., $v_{n}$ ${\ displaystyle v_ {n}}$ $v_ {n}$ și atribuie către $v_{i}$ ${\ displaystyle v_ {i}}$ $tu}$ cea mai mică culoare disponibilă nefolosită de vecinii din $v_{i}$ ${\ displaystyle v_ {i}}$ $tu}$ între $v_{1}$ ${\ displaystyle v_ {1}}$ $v_1$ , ..., $v_{i-1}$ ${\ displaystyle v_ {i-1}}$ $v _ {{i-1}}$ , adăugând o nouă culoare dacă este necesar. Calitatea colorării rezultate depinde de sortarea aleasă. Există o ordine care duce la o colorare greedy (în engleză greedy coloring) cu numărul optim de $\chi (G)$ ${\ displaystyle \ chi (G)}$ $\ chi (G)$ culori. Pe de altă parte, culorile lacome pot fi în mod arbitrar greșite; de exemplu, graficul coroană de pe n vârfuri poate fi bicolor, dar are o ordonare care duce la colorarea lacomă cu $n/2$ ${\ displaystyle n / 2}$ $n / 2$ culori.

Dacă vârfurile $v_{i}$ ${\ displaystyle v_ {i}}$ $tu$ sunt ordonate în funcție de rangul lor $d(v_{i})$ ${\ displaystyle d (v_ {i})}$ ${\ displaystyle d (v_ {i})}$ , colorarea lacomă rezultată se folosește la maximum ${\displaystyle \max _{i}}({\text{min}}\{d(v_{i})+1,i\})$ ${\ displaystyle {\ displaystyle \ max _ {i}} ({\ text {min}} \ {d (v_ {i}) + 1, i \})}$ ${\ displaystyle {\ displaystyle \ max _ {i}} ({\ text {min}} \ {d (v_ {i}) + 1, i \})}$ culori, cel mult unul mai mult decât gradul maxim al graficului. Această euristică este uneori numită algoritmul Welsh - Powell. ^[11] O altă euristică datorată lui Brélaz stabilește ordinea dinamic pe măsură ce algoritmul continuă, alegând apoi vârful adiacent celui mai mare număr de culori diferite. ^[12] Multe alte euristici pentru colorarea graficelor se bazează în mod similar pe colorarea lacomă pentru o strategie specifică de ordonare a vârfurilor statice sau dinamice; acești algoritmi sunt uneori numiți algoritmi de colorare secvențială .

Algoritmi paraleli și distribuiți

În domeniul algoritmilor distribuiți , colorarea graficelor este strâns legată de problema ruperii simetriei . Algoritmii randomizați de ultimă generație sunt mai rapizi decât algoritmii deterministi pentru un grad maxim suficient de mare Δ. Cei mai rapizi algoritmi randomizați folosesc tehnica multiprove Schneider și colab. ^[13]

Într-un grafic simetric , un algoritm determinist distribuit nu poate găsi o culoare exactă a vertexului. Sunt necesare câteva informații pentru a sparge simetria. O presupunere tipică este că inițial fiecare nod are un identificator unic , de exemplu, din setul {1, 2, ..., n }. Cu alte cuvinte, presupunem că ni se dă o culoare n . Provocarea este de a reduce numărul de culori de la n la, de exemplu, Δ + 1. Se folosesc mai multe culori, de exemplu. O (Δ) în loc de Δ + 1, sunt necesare mai puține sesiuni de comunicare. ^[13]

O versiune directă distribuită a versiunii algoritmului lacom pentru colorarea (Δ + 1) necesită Θ ( n ) sesiuni de comunicare în cel mai rău caz - informațiile pot fi propagate dintr-o parte a rețelei în alta.

Cel mai simplu caz interesant este un ciclu n . Richard Cole și Uzi Vishkin ^[14] arată că există un algoritm distribuit care reduce numărul de culori de la n la O (log n ) într-o singură etapă de comunicare sincronă. Prin iterația aceleiași proceduri, este posibil să se obțină o 3-colorare a unui ciclu n în etapele de comunicare O (log * n ) (presupunând că avem identificatori de nod unici).

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

Tehnica lui Cole și Vishkin poate fi aplicată și graficelor cu un grad limitat arbitrar; timpul de rulare este poli (Δ) + O (log * n ). ^[15] La tecnica fu estesa ai grafi con dischi unitari di Schneider et al. ^[16] Gli algoritmi deterministici più veloci per la (Δ + 1)-colorazione di un piccolo Δ sono dovuti a Leonid Barenboim, Michael Elkin e Fabian Kuhn. ^[17] L'algoritmo di Barenboim et al. si svolge nel tempo O (Δ) + log*( n )/2, che è ottimale in termini di n poiché il fattore costante 1/2 non può essere migliorato a causa del limite inferiore di Linial. Panconesi et al. ^[18] usano le somposizioni a rete per computare una Δ+1 colorazione nel tempo $2^{O({\sqrt {\log n}})}$ $2^{O({\sqrt {\log n}})}$ $2^{{O({\sqrt {\log n}})}}$ .

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

Algoritmi decentralizzati

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

Complessità computazionale

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

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

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

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

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. ^[27] In termini di algoritmi di approssimazione, l'algoritmo di Vizing mostra che il numero cromatico degli spigoli può essere approssimato entro 4/3, e il risultato della difficoltà mostra che non esiste nessun algoritmo (4/3 − ε ) per un qualsiasi ε > 0 a meno che P = NP . Questi sono tra i più vecchi risultati nella letteratura degli algoritmi di approssimazione, anche se nessuno dei due studi fa uso esplicito di quella nozione. ^[28]

Applicazioni

Schedulazione

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

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

Allocazione dei registri

Lo stesso argomento in dettaglio: Allocazione dei registri .

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

L'approccio dei libri di testo a questo problema è di modellarlo come un problema di colorazione dei grafi. ^[30] 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

Lo stesso argomento in dettaglio: Teoria di Ramsey .

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

Altre colorazioni

Colorazione per lista: Ciascun vertice sceglie da una lista di colori
Colorazione degli spigoli per lista: Ciascuno spigolo sceglie da una lista di colori
Colorazione totale: Sono colorati i vertici e gli spigoli
Colorazione armoniosa: Ogni coppia di colori appare su almeno un vertice
Colorazione totale: Ogni coppia di colori appare su almeno uno spigolo
Colorazione esatta: Ogni coppia di colori appare su esattamente uno spigolo
Colorazione aciclica: Ogni sottografo 2-cromatico è aciclico
Colorazione a stella: Ogni sottografo 2-cromatico è una collezione disgiunta di stelle
Colorazione forte: Ogni colore appare in ogni partizione di uguale dimensione esattamente una volta
Colorazione forte degli spigoli: Gli spigoli sono colorati in modo che ciascuna classe di colore induce un accoppiamento (equivalente a colorare il quadrato del grafo lineare)
Colorazione equilibrata: Le dimensioni delle classi di colore differiscono almeno di uno
T-colorazione: La distanza tra due colori di vertici adiacenti non deve appartenere all'insieme fisso T

Colorazione per rango: Se due vertici hanno lo stesso colore i , allora ogni cammino fra di essi contiene un vertice con colore maggiore di i
Colorazione degli spigoli a intervalli: Un colore di spigoli che si incontrano in un vertice comune deve essere contiguo
Colorazione circolare: Motivata dai sistemi di compiti nei quali la produzione produce in modo ciclico
Colorazione dei cammini: Modella un problema ricorrente nei grafi
Colorazione frazionata: I vertici possono avere molteplici colori, e su ciascuno spigolo la somma delle parti dei colori di ciascun vertice non è maggiore di uno
Colorazione orientata: Prende in considerazione l'orientazione degli spigoli del grafo
Cocolorazione: Una colorazione impropria dei vertici dove ogni classe di colore induce un insieme indipendente o una cricca
Sottocolorazione: Una colorazione impropria dei vertici dove ogni classe di colore induce un'unione di cricche
Colorazione difettosa: Una colorazione impropria dei vertici dove ogni classe di colore induce un sottografo di grado vincolato
Colorazione debole: Una colorazione impropria dei vertici dove ogni nodo non isolato ha almeno un vicino con un colore diverso
Colorazione per somma: Il criterio di minimalizzazione è la somma dei colori
Colorazione totale con distinzione dei vertici adiacenti: Una colorazione totale con la restrizione aggiuntiva che qualsiasi due vertici adiacenti hanno insiemi di colori diversi
Colorazione centrata: Ogni sottografo indotto connesso ha un colore che si è usato esattamente una volta

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

Note

^ M. Kubale, History of graph coloring , in Kubale (2004)
^ van Lint & Wilson (2001) , cap. 33 .
^ Jensen & Toft (1995) , p. 2
^ Brooks (1941) .
^ ^a ^b Björklund, Husfeldt & Koivisto (2009) .
^ Lawler (1976) .
^ Beigel & Eppstein (2005) .
^ Fomin, Gaspers & Saurabh (2007) .
^ Wilf (1986) .
^ Sekine, Imai & Tani (1995) .
^ Welsh & Powell (1967) .
^ Brélaz (1979) .
^ ^a ^b Schneider (2010) .
^ Cole & Vishkin (1986) , vedi anche Cormen, Leiserson & Rivest (1990) , Sezione 30.5
^ Goldberg, Plotkin & Shannon (1988) .
^ Schneider (2008) .
^ Barenboim & Elkin (2009) ; Kuhn (2009)
^ Panconesi (1995) .
^ Garey, Johnson & Stockmeyer (1974) ; Garey & Johnson (1979) .
^ Dailey (1980) .
^ Halldórsson (1993) .
^ Zuckerman (2007) .
^ Guruswami & Khanna (2000) .
^ Khot (2001) .
^ Jaeger, Vertigan & Welsh (1990) .
^ Goldberg & Jerrum (2008) .
^ Holyer (1981) .
^ Crescenzi & Kann (1998) .
^ Marx , (2004) .
^ Chaitin (1982) .

Bibliografia

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

Altri progetti

Wikimedia Commons contiene immagini o altri file su Colorazione dei grafi

Collegamenti esterni

( EN ) Graph Coloring Page by Joseph Culberson (graph coloring programs)
( EN ) CoLoRaTiOn by Jim Andrews and Mike Fellows is a graph coloring puzzle
( EN ) Links to Graph Coloring source codes , su adaptivebox.net .
( EN ) Code for efficiently computing Tutte, Chromatic and Flow Polynomials Archiviato il 16 aprile 2008 in Internet Archive . by Gary Haggard, David J. Pearce and Gordon Royle
( EN ) Graph Coloring Web Application , su graph-coloring.appspot.com .

Controllo di autorità	LCCN ( EN ) sh2004000285

Portale Matematica : accedi alle voci di Wikipedia che trattano di Matematica

[1] M. Kubale, History of graph coloring , in Kubale (2004)

[2] van Lint & Wilson (2001) , cap. 33 .

[3] Jensen & Toft (1995) , p. 2

[4] Brooks (1941) .

[bhk-5] Björklund, Husfeldt & Koivisto (2009) .

[6] Lawler (1976) .

[7] Beigel & Eppstein (2005) .

[8] Fomin, Gaspers & Saurabh (2007) .

[9] Wilf (1986) .

[10] Sekine, Imai & Tani (1995) .

[11] Welsh & Powell (1967) .

[12] Brélaz (1979) .

[Schneider_2010-13] Schneider (2010) .

[14] Cole & Vishkin (1986) , vedi anche Cormen, Leiserson & Rivest (1990) , Sezione 30.5

[15] Goldberg, Plotkin & Shannon (1988) .

[16] Schneider (2008) .

[17] Barenboim & Elkin (2009) ; Kuhn (2009)

[18] Panconesi (1995) .

[19] Garey, Johnson & Stockmeyer (1974) ; Garey & Johnson (1979) .

[20] Dailey (1980) .

[21] Halldórsson (1993) .

[22] Zuckerman (2007) .

[23] Guruswami & Khanna (2000) .

[24] Khot (2001) .

[25] Jaeger, Vertigan & Welsh (1990) .

[26] Goldberg & Jerrum (2008) .

[27] Holyer (1981) .

[28] Crescenzi & Kann (1998) .

[29] Marx , (2004) .

[30] Chaitin (1982) .

[1]

[2]

[3],

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]