Bojenje grafova

U teoriji grafova, bojenje grafova je specijalan slučaj obeležavanja grafova; ono predstavlja dodeljivanje oznaka, koje se uobičajeno nazivaju "boje", elementima grafa nad kojim postoje određena ograničenja. U svom najjednostavnijem obliku, to predstavlja način bojenja čvorova grafa, tako da nikoja dva susedna čvora ne budu obojena istom bojom; ovo se naziva bojenje čvorova. Na sličan način, bojenje grana dodeljuje boju svakoj grani tako da nikoje dve susedne grane nisu obojene istom bojom, a bojenje oblasti planarnog grafa predstavlja dodeljivanje boja svakoj oblasti (regiji) tako da nikoje dve oblasti koje imaju zajedničku granu nisu obojene istom bojom.

Bojenje čvorova predstavlja početni problem izučavanja ove oblasti i svi ostali problemi bojenja se mogu svesti na njega. Na primer, bojenje grana nekog grafa predstavlja bojenje čvorova linearnog grafa, a bojenje oblasti planarnog grafa može se predstaviti kao bojenje čvorova njemu odgovarajućeg dvostrukog grafa. Međutim, problemi bojenja koji nisu zadati u obliku bojenja čvorova se najčešće proučavaju onako kako su zadati. Ovo je delom zbog perspektive, a delom zbog toga što se neki problemi najbolje rešavaju u svom izvornom obliku, kao na primer bojenje grana.

Dogovor o korišćenju boja vodi poreklo od bojenja država na mapi, gde je svaka oblast morala biti obojena. Ovo je svedeno na bojenje oblasti planarnih grafova. Na osnovu planarne dualnosti to je dalje svedeno na bojenje čvorova i u ovakvoj formi može se primeniti na sve grafove. U matematičkoj i kompjuterskoj reprezentaciji, uobičajeno se koriste prvih nekoliko pozitivnih ili nenegativnih celih brojeva kao "boja". Za set boja se može koristiti bilo koji konačan skup brojeva. Priroda problema zavisi isključivo od broja boja, a ne od konkretne boje.

Bojenje grafova ima široku praktičnu kao i teorijsku primenu. Osim uobičajenih vrsta problema, na problem bojenja mogu se zadati drugačija ograničenja u vidu načina dodele boja ili u vidu korišćenja konkretnih boja. Ono uživa veliku popularnost javnosti u vidu popularne igre Sudoku. Bojenje grafova je i dalje jako aktivna oblast istraživanja.

Ispravno bojenje Petersenovog grafa sa 3 boje, što je ujedno i minimalno rešenje.

Istorija

Prvi rezultati u oblasti bojenja grafova su isključivo bili povezani sa planarnim grafovima u vidu bojenja mapa. Dok je pokušavao da oboji okruge na mapi Engleske, Francis Gutrije (en. Francis Guthrie) je izneo je pretpostavku o četiri boje, koja kaže da su četiri boje dovoljne da se cela mapa oboji tako da nikoja dva susedna okruga nisu obojena istom bojom. Gutrijeov brat je prosledio ovu pretpostavku svom profesoru matematike Avgustusu de Morganu (en. Augustus de Morgan) na Londonskom univerzitetu, koji je ovo spomenuo Vilijamu Hamiltonu (en. William Hamilton) 1852. godine. Artur Kejli (en. Arthur Cayley) je izneo ovaj problem na sastanku Društva matematičara Londona 1879. godine. Iste godine, Alfred Kemp (en. Alfred Kempe) objavio je naučni rad koji je tvrdio da je dokazao ispravnost, i u narednoj deceniji problem četiri boje je smatran rešenim. Za svoje dostignuće Kemp je proglašen za člana Kraljevskog društva, a kasnije i za predsednika Društva matematičara Londona.

1890. godine, Hejvud (en. Heawood) je istakao da Kempovo tvrđenje nije ispravno. Međutim, u svojoj studiji, dokazao je teoremu o pet boja, prema kojoj bilo koja planarna mapa može biti obojena sa ne više od pet boja, koja je bila inspirisana Kempovim idejama. U narednom veku, velika količina naučnog rada i teorija je razvijana kako bi se broj boja smanjio na četiri, sve dok teorema o četiri boje konačno nije bila dokazana 1976. godine od strane Keneta Epla(en. Kenneth Appel) i Volfganga Hakena (en. Wolfgang Haken). Dokaz se vratio idejama Hejvuda i Kempa. Dokaz teoreme o četiri boje je takođe vredan pažnje jer je prvi veliki kompjuterski potpomognut dokaz.

1912. godine, Džordž Dejvid Birkhof (en. George David Birkhoff) je uveo hromatski polinom u studiju o problemu bojenja, koji je sveden na Tatov polinom (en. Tutte) zasnovan na važnim Tatovim strukturama u algebarskoj teoriji grafova. Kemp je već skrenuo pažnju na generalni, neplanarni slučaj 1879. godine, koji je u ranom 20. veku rezultirao svođenjem bojenja planarnih grafova na bojenje površina većeg reda.

1960. godine, Klod Berž (en. Claude Berge) je formulisao još jednu pretpostavku o bojenju grafova, jaku pretpostavku o perfektnim grafovima, koji je izvorno bio motivisan informaciono-teoretskom konceptu koji se zove nula-greška kapaciteta grafa koji je uveo Šenon (en. Shannon). Pretpostavka je ostala nerešena četrdeset godina, sve dok nije bila utvrđena kao proslavljena jaka teorema o prefektnim grafovima Čudnovskog, Robertsona, Simora i Tomasa 2002. godine.

Bojenje grafova je bilo proučavano kao algoritamski problem još od početka 1970-ih: hromatski numerički problem je jedan od Karpovih 21 NP-kompletnih problema iz 1972. godine i otprilike u isto to vreme su razvijeni razni algoritmi u eksponencijalnom vremenu, zasnovani na bektrekingu i na Zikovljevom (ru. Zыkov) algoritmu brisanja kontrakcija iz 1949.Jedna od glavnih primena bojenja grafova, alokacija registara u kompajlerima, predstavljena je 1981. godine.

Definicija i terminologija

Ovaj graf može biti 3-obojen na 12 načina.

Bojenje čvorova

Kada se koristi bez ikakvih kvalifikacija, bojenje grafa je skoro uvek pravilno bojenje čvorova, naime, obeležavanje čvorova grafa na taj način da nikoja dva susedna čvora nisu obojena istom bojom. Pošto se čvor sa petljom nikada ne može pravilno obojiti, jasno je da su grafovi, korišćeni u ovom kontekstu, bez petlji.

Terminologija korišćenja boja za obeleživanje čvorova vodi poreklo od problema bojenja oblasti na mapama. Boje poput crvene i plave se koriste samo kada je broj korišćenih boja mali i uobčajeno je da se brojčane oznake uzimaju iz skupa prirodnih brojeva {1, 2, 3, ...}.

Bojenje korišćenjem najviše k boja, naziva se (pravilno) k-bojenje. Najmanji broj boja, potreban da bi se obojio graf G se naziva hromatskim brojem grafa G i označava se sa χ(G). Ponekad se može naći i oznaka γ(G), pošto se χ(G) takođe koristi za predstavljanje Ojlerove karakteristike grafa. Graf koji se može obojiti sa (pravilnim) k bojenjem se naziva k-obojiv. Graf je k-hromatski ako je njegov hromatski broj k. Skup čvorova kojima je dodeljena ista boja se naziva klasa te boje, svaka takva klasa formira nezavisni skup. Prema tome, k-bojenje je isto što i podela čvorova grafa na nezavisne skupove čvorova iste boje, iz čega proističe da termini k-partitan i k-obojiv imaju isto značenje.

Hromatski polinom

Hromatski polinom je broj različitih načina na koji dati graf može biti obojen koristeći ne više od proizvoljno zadatog broja boja. Na primer, koršćenjem tri boje, graf sa slike desno može biti obojen na 12 različitih načina. Ukoliko bi se koristile dve boje, graf ne bi uopšte mogao biti obojen. Sa četiri boje, može biti obojen na 24 + 4*12 = 72 načina: korišćenjem sve 4 boje postoji 4! = 24 ispravna bojenja, a za svaki izbor tri od četiri boje ima 12 ispravnih 3-bojenja. Tako da, za graf iz primera tablica pravilnih bojenja izgleda ovako:

Dozvoljene boje	1	2	3	4	…
Broj bojenja	0	0	12	72	…

Hromatski polinom je funkcija P(G, t) koja izračunava broj t-bojenja grafa G. Kao što mu ime kaže, za dati graf G funkcija je zaista polinomijalna za t. Na primer, za graf P(G, t) = t(t-1)²(t-2) i to je zaista P(G, 4) = 72. Hromatski polinom uključuje najmanje istu količinu datih informacija o bojivosti grafa G kao i njegov hromatski broj. Zaista, χ je najmanji prirodan broj koji nije jednak korenu hromatskog polinoma. (slika)

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

Hromatski polinomi za određene grafove

Trougao K3	$t(t-1)(t-2)$
Potpun graf Kn	$t(t-1)(t-2)\cdots (t-(n-1))$
Stablo sa n čvorova	$t(t-1)^{n-1}$
Cikl Cn	$(t-1)^{n}+(-1)^{n}(t-1)$
Petersonov graf	$t(t-1)(t-2)(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t-352)$

Bojenje grana

Bojenje grana grafa je pravilno bojenje ivica grafa, što znači da nikoje dve susedne grane nisu obojene istom bojom. Bojenje grana sa k boja se naziva k-bojenje-grana i to je ekvivalentno problemu deljenja grana u ukupno k skupova. Najmanji broj boja potreban za bojenje grana grafa G se naziva hromatski indeks ili hromatski broj grana, χ'(G). Tejt bojenje (en. Tait) je 3-bojenje-ivica kubnog grafa. Teorema o četiri boje je ekvivalentna pretpostavci da svaki planarni kubni graf bez mosta priznaje Tejt bojenje.

Potpuno bojenje

Potpuno bojenje je vrsta bojenja čvorova i grana grafa. Kada se koristi bez ikakvih ograničenja, pretpostavlja se da je potpuno bojenje pravilno, što znači da susedni čvorovi i grane nisu obojeni istom bojom. Potpuni hromatski broj χ(G) grafa G je najmanji broj boja potreban za bilo koje potpuno bojenje grafa G.

Neoznačeno/neobeleženo bojenje

Neoznačeno/neobeleženo bojenje je bojenje pod uticajem automorfizma skupa grafova. Ako bismo interpretirali bojenje grafa na čvorove kao vektor u prostoru, automorfizam bi bio broj permutacija koeficijenata bojenja. Postoji analogija sa hromatskim polinomom koji izračunava broj bojenja grafa datim konačnim skupom boja.

Osobine

Ograničenja hromatskog broja

Dodejljivanje pojedinačne boje svakom pojedinačnom čvoru uvek kao rezultat daje ispravno bojenje pa je

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

Jedini grafovi koji su jedno-obojivi su grafovi bez grana. Kompletan graf $K_{n}$ sa n čvorova zahteva $\chi (K_{n})=n$ boja. U optimalnom bojenju mora postojati barem jedna od m grana grafa između svakog para isto obojenih čvorova, pa važi

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

Ako G sadrži kliku vreličine k, onda je potrebno barem k boja za bojenje te klike, drugim rečima, hromatski broj je uvek veći ili jednak veličini klike.

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

Dvoobojivi grafovi su tačno biparitni grafovi, uključujući i stabla i šume. Po teoremi o četiri boje, svaki planaran graf može biti četiri-obojiv Pohlepno bojenje pokazuje da svaki graf može biti obojen sa jednom više bojom u odnosu na maksimalan stepen čvora u grafu.

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

Kompletni grafovi imaju $\chi (G)=n$ i $\Delta (G)=n-1$, grafovi sa neparnim ciklusima imaju $\chi (G)=3$ i $\Delta (G)=2$. Tako da je za ovakve grafove ovo rešenje najbolje moguće. U svim drugim slučajevima, granica se može malo poboljšati ; Brokova teorema tvrdi da je$\chi (G)\leq \Delta (G)$ za povezan, prost graf G, osim ako je G kompletan graf ili ima neparan ciklus

Grafovi sa visokim hromatskim brojem

Grafovi sa velikim brojem klikova imaju visok hromatski broj, ali obrnuto ne važi. Grečeov graf je primer četiri-hromatskog grafa bez trougla, pa se ovaj primer može uopštit na Mickelskijevu teoremu

Mickelskijeva teorema:Postoje grafovi proizvoljno visokog hromatskog broja bez trouglova.

Iz Brokove teoreme sledi da graf sa visokim hromatskim brojem mora imati visok maksimalni stepen čvora. Još jedno od lokalnih svojstava iz kog proizilazi visok hromatski broj je prisustvo velike klike. Međutim obojivost nije u potpunosti lokalni fenomen: graf sa visokim obimom lokalno izgledaju kao stabla zato što su svi ciklusu dugi, ali njegov hromatski broj ne mora biti 2:

Teorema(Erdos): Postoji graf sa proizvoljno visokim obimom i hromatskim brojem.

Ograničenja hromatskog indeksa

Bojenje grana grafa G može se predstaviti kao bojenje njegovog linijskog grafa$L(G)$, i obrnuto. Stoga:

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

Postoji uska povezanost između obojivosti grana grafa i maksimalnog stepena $\Delta (G)$. Pošto su sve grane incidentne sa istim čvorom njihove boje moraju biti različite. Pa važi:

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

Šta više,

Keningova teorema: $\chi '(G)=\Delta (G)$ ako je G bipartitan.

Uopšteno, povezanost je veća nego ona koju nudi Brokova teorema za bojenje čvorova:

Vizingova teorema: Grafu sa maksimalnim stepenom $\Delta$ hromatski broj grana jednak je $\Delta$ ili $\Delta +1$.

Druga svojstva

Graf je k-obojiv ako i samo ako ima acikličnu orijentaciju u kojoj najduži put ima najviše dužinu k. Ovo je Galai-Has-Roj-Vitaver teorema.

O beskonačnim grafovima mnogo manje nam je poznato.

Ako su svi konačni podgrafovi beskonačnog grafa G k-obojivi, onda je i G, pod pretpostavkom aksiome izbora. Ovo je de Brujin-Erdos teorema.

Ako graf potpuno n-bojenje za svako n ≥n₀, onda je graf beskonačno potpuno obojiv.

Algoritmi

Polinomijalno vreme

Određivanje da li graf može biti obojen sa dve boje je ekvivalentno ispitivanju da li je graf bipartitan, i može se uraditi u linearanom vremenu koristeći BFS(pretraga u širinu). Opširnije, hromatski broj i odgovarajuća boja savršenog grafa može se izračunati korišćenjem semidefinitnog programiranja. Konačne formule hromatskih polinoma poznate su za mnoge klase grafova kao što su šume, kordski grafovi, ciklovi, točkovi, stepenice, tako da se oni mogu izračunati u polinomijalnom vremenu.

Ako je graf planaran i ima malu širinu grana (ili je neplanaran ali sa poznatom dekompozicijom grana), tada može biti rešen u polinomijalnom vremenu koristeći dinamičko programiranje. Uglavnom, vreme potrebno je polinomijalno u odnou na veličinu grafa, ali je eksponencijalno u odnosu na širinu grana.

Egzaktni algoritmi

Pretraga grubom silom za k-bojenje zahteva $k^{n}$ dodela boja svakom od n čvorova i proverava da li je rezultat korektan. Računati hromatski broj i hromatski polinom, ova procedura se koristi za sve $k=1,\ldots ,n-1$ i ne praktično je za sve osim za grafove veoma male vrste.

Korišćenjem dinamičkog programiranja i postavljanjem granice maksimalnog broja nezavisnih setova, k-obojivost se može odrediti sa vremenskom i prostornom složenošću $O(2.445^{n})$. Korišćenjem principa inkluzije-ekskluzije i Jejtsovog algoritma za brze zeta transformacije, k-obojivost može se odrediti u $O(2^{n}n)$ za bilo koje k. Brži algoritmi su poznati za 3- i 4-obojivost, koji imaju vremensku složenost $O(1.3289^{n})$ i $O(1.7272^{n})$.

Kontrakcija

Kontrakcija $G/uv$ grafa G je graf dobijen odrađivanjem čvorova u i v , uklanjanjem svih grana između ta dva čvora i zamenjivanjem sa jednim čvorom w tako da sve grane koje su bile incidentne sa u i v sada budu incidentne sa w. Ova operacija ima važnu ulogu u analizi bojenja grafa.

Hromatski broj zadovoljava sledeću rekurentnu relaciju:

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

prema Zikovu, gde su u i v ne susedni čvorovi, $G+uv$ je graf sa dodatom granom $uv$. Nekoliko algoritama su bazirani na ovoj rekurentnoj relaciji, i drvo koje se dobija kao rezultat izvršavanja se nazivaj još i Zikovljevo drvo. Vreme izvršavanja se bazira na heuristici odabira čvorova u i v.

Hromatski polinom zadovoljava sledeću rekurentnu relaciju:

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

Gde su u i v susedni čvorovi i $G-uv$ je graf bez grane $uv$. $P(G-uv,k)$ predstavlja broj mogućih ispravnih bojenja grafa kada čvorovi mogu imati iste ili različite boje. Broj ispravnih bojenja dobijamo kao sumu dva grafa. Ako čvorovi u i v imaju različite boje. Onda takođe možemo razmatrati i graf gde su u i v susedne. Ako u i v imaju istu boju, onda možemo razmatrati graf u kom su u i v kontrakovane. Tutova radoznalost o tome koje još osobine grafa zadovoljava rekurentna jednačina dovela ga je do otkrića bivariantne generalizacije hromatskog polinoma, Tatovog polinoma.

Prethodne činjenice dovele su do nastanka rekurzivne procedure algoriritam brisanje-kontrakcija, koji formira bazu za mnoge algoritme bojenja grafa. Vremenska složenost zadovoljava istu rekurentnu jednačinu kao i fibonačijev niz, pa je u najgorem slučaju formula za n čvorova i m grana. Analiza se može ubrzati do polinomijalnog faktora $((1+{\sqrt {5}})/2)^{n+m}=O(1.6180^{n+m})$razapinjućih stabala ulaznog grafa. U praksi, strategije separacije i evaluacije i odbijanje grafovskih izomorfizama se koriste da bi se izbegli neki od rekurzivnih poziva, a vreme izvršavanja zavisi od heuristike korišćene za odabir čvorova.

Pohlepno bojenje

Dva različita pohlepna bojenja istog grafa korišćenjem različitih preosleda. Polepni algoritam je desni primer grafa sa n čvorova obojio sa $n/2$ boja iako je graf 2-obojiv.

Pohlepni algoritam razmatra čvorove u određenom redosledu $v_{1}$,…,$v_{n}$ gde se čvoru $v_{i}$ dodeljuje najmanja moguća boja koja nije dodeljena njegovim susedima ili se uvodi nova boja ukoliko je neophodna. Kvalitet bojenja zavisi od izabranog redosleda. Postoji bojenje sa optimalnim brojem $\chi (G)$ boja. U nekim slučajevima bojenje može ispasti lošije; primer je Kruna(graf) sa n čvorova koji može biti obojen korišćenjem 2 boje, ali postoji i redosled koji dovodi bojenja sa sa $n/2$ boja.

Za kordijske grafove, i neke njegove posebne slučajeve kao što su intervalski grafovi i indfirentni grafovi, pohlepni algoritam se može upotrebiti za određivanje optimalnog bojenja u polinomijalnom vremenu izborom redosleda čvorova koji je inverzan savršenom redosledu uklanjanja tog grafa. Savršeno uredivi grafovi uopštavaju ovo svojstvo, ali je NP-teško naći savršeno bojenje tih grafova.

Ako su čvorovi poređani po stepenu čvora, rezultat pohlepnog algoritma koristi najviše ${\text{max}}_{i}{\text{ min}}\{d(x_{i})+1,i\}$ boja, najviše za jednuboju više od najvećeg stepena čvora u grafu. Ova heuristika se naziva još i Velš-Povel algoritam. Još jednu heuristiku zasnovao je Brelaz gde se redosled određuje dinamički tokom izvršavanja programa, sledeći čvor se bira tako da bude susedan najvećem broju različitih boja. Mnogi drugi algoritmi zasnivaju se na statičkom ili dinamičkom određivanju redosleda čvorova i takvi algoritmi se nazivaju još i algoritmi sekvencijalnog bojenja.

Paralelni i distriburani algoritmi

U oblasti distribuiranih algoritama, bojenje grafova je blisko razbijanju simetrija. Trenutni algoritmi za randomizaciju su brži od determinističkih algoritama za dovoljno veliki maksimalni stepen grafa. Najbrži algoritmi za randomizaciju koriste tehniku vešestrukih pokušaja koji je zasnova Šnajder.

U simetričnom grafu, deterministički distribuirani algoritmi ne mogu da pronađu ispravno bojenje čvorova. Standardna pretpostavka je da svaki čvor ima jedinstveni identfikator – broj od 1...n. Pretpostavimo da je n boja potrebno da se oboji graf Izazov je smanjiti broj sa n na npr. maksimalni stepen grafa uvećan za 1.

Pravolinijski distribuirana verzija pohlepnog algoritma za $\Delta +1$ -bojenje zahteva Θ(n)komunikacionih rundi u najgorem slučaju – informacije potencijalno moraju biti slate sa jednog na drugi kraj mreže.

Najjednostavjniji interesantan primer je n-ciklus. Ričar Kol i Uzi Viškin su pokazali distribuirani algoritam koji redukuje broj boja sa n na O(logn) u jednom sinhronom komunikacionom koraku. Ponavljanjem iste procedure moguće je izdvojiti 3-bojenje n-cikla u O(log*n) komunikacionih korak(pod pretpostavkom da imamo jedinstvene identifikatore).

Funkcija log*, iterativni logaritam, je ekstremno sporo rastuća funkcija, „Skoro konstantna“. Zbog ovoga su Kol i Viškin postavili pitanje postojanja algoritma koji u konstantnom vremenu izračunava 3-obojivost n-cikla. Linial je 1992. Godine dokaza da nije moguće: bilo koji deterministički distribuiran algoritam zahteva Ω(log*n) komunikacionih koraka da redukuje n-bojenje na 3-bojenje n-cikla.

Problem bojenja stranica se takođe proučavao u distribuiranom modelu. Pankonezi i Rici (2001) su dostigli (2 Δ -1) bojenje u O(Δ + log*n) vremenu u ovom modelu. Distribuirano bojenje čvorova se po Linialu primenjuje i na bojenje stranica.

Decentralizovani algoritmi

Decentralizovani algoritmi su oni u kojima nikakvo prosleđivanje poruka nije dozvoljeno(kontrast distribuiranim algoritmima gde se vrši slanje poruka). Postoje i efikasni decentralizovani algoritmi. Algoritam se zasniva na tome da čvor zna dali je njegov sused označen istom bojom tj, da li postoji konflikt. Ovo je dovoljno da algoritmizasnovani na veštačkoj inteligenciji odrede bojenje grafa.

Složenost izračunavanja

Bojenje grafova je kompjuterski teško. To je NP-kompletan problem ako se graf treba obojiti sa k boja, osim kada je k=1 i k=2. Konkretno, NP-težak problem je izračunavanje hromatskog broja. 3-bojenje ostaje NP-kompletan problem čak i kada se rešava planaran graf stepena 4.

Najbolji poznat algoritam za aproksimaciju izračunava bojenje veličine najviše faktor O(n(log n)⁻³(log log n)²) hromatskog broja. Za sve ε> 0, aproksimisanje hromatskog broja na $n^{1-\epsilon }$ je NP-težak problem.

Takođe je NP-težak problem bojenja 3-obojivog grafa sa 4 boje i k-obojivog grafa sa knalog.. boja za dovoljno veliko k.

Za bojenje stranica, Vizingov dokaz daje algoritam koji koristi najviše Δ+1 boja. Međutim izbor jednog od dva kandidata vrednosti za hromatski broj stranica je NP-kompletan problem. U terminima aproksimacionih algoritama, Vizingov algoritam pokazuje da se hromatski broj stranice može aproksimizovati do na $4/3$ , i dokazano je da ne postoji algoritam $(4/3-\epsilon )$ za bilo koje ε > 0.

Primene

Usmeravanje

Bojenje čvorova modeluje nekoliko problema usmeravanja. U najčistijem obliku, datom kompletu zadataka treba da se dodele vremenski termini, tako da svaki zadatak dobije po jedan takav termin. Zadaci mogu biti raspoređeni u bilo kom redosledu, ali parovi zadataka mogu biti u sukobu u smislu da ne mogu biti budu raspoređeni u istom terminu, na primer zato što se oslanjaju na isti izvor. Odgovarajući graf sadrži čvor ѕa svaki zadatak i granu ѕa svaki sukobljen par zadataka. Hromatski broj grafa je tačno najmanji raspon, optimalno vreme potrebno da se završe svi zadaci bez sukoba.

Detalji problema usmeravanja definišu strukturu grafa. Na primer, pri dodeli letova vazdušsnom saobraćaju, rezultujući graf je graf intervala, pa se problem bojenja može efikasno rešiti. Pri alokaciji protoka radio na stanicama, rezultujući graf je graf jediničnog diska, pa je problem bojenja 3-približan.

Registarska alokacija

Kompajler je kompjuterski program koji prevodi jedan kompjuterski jezik u neki drugi. Da bi se poboljšalo vreme izvođenja rezultujućeg koda, jedna od tehnika optimizacije je registarska alokacija, gde se najkorišćenije vrednosti prevedenog programa čuvaju u registrima procesora. Idealno, vrednosti se dodeljuju registrima da bi ostali u registrima i posle upotrebe.

Školski pristup ovom problemu je da se modeluje kao i problem bojenja grafova. Kompajler konstruiše graf, gde su čvorovi promenljive i grana povezuje dva čvora ako su potrebni istovremeno. Ako graf može biti obojen sa k bojaonda bilo koja kombinacija potrebnih istovremeno može da se uskladišti u najviše k registara.

Druge primene

Problem bojenja grafa nalazi mnoge primene, uključujući i uklapanje obrazaca.

Zabavna slagalica Sudoku može se videti kao rešavanje problema bojenja grafa sa 81-im čvorom sa 9 boja.

Ostala bojenja

Remzijeva teorija

Važna klasa nepravilnih problema bojenja proučava se u Remzijevoj teoriji, gde se granama grafa dodeljuju boje, i nema ograničenja pri bojenju incidentnih grana. Jednostavan primer je teorema o prijateljstvu, koja navodi da će pri bojenju grana K6 kompletnog grafa sa šest čvorova se pojaviti jednobojni trougao; često opisana govoreći da svaka grupa od šestoro ljudi sadrži tri zajednička stranca ili tri zajednička poznanika. Remzijeva teorija se bavi generalizovanjem ove ideje, tražeći uopštene uslove za postojanje jednobojnih podgrafova sa datom strukturom.

Reference

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