BARVAiSIJA TOČK GRAFOV 
INFORMATICA1/85 
VLADIMIR BATAGELJ 
UDK: 519.174 UNIVERZA EDVARDA KARDELJA V LJUBLJANI 
FAKULTETA ZA NARAVOSLOVJE IN TEHNOLOGIJO 
VTO MATEMATIKA IN MEHANIKA 
v seistavku je podan pregled najpomembnejših rezultatov o teoretičnih in algoritraicnih 
vidikih problema barvanja grafov. Na koncu je podan postopek, ki združuje trenutno 
najuspešnejša hevristična postopka za barvanje grafov: Szekeres-Wilfov in Brelazov 
postopek. 
GRAPH COLORIHG 
in the paper a survey of the mist important results on theoretic and algorlthmio aspects 
of the graph ooloring problem is given. A heuristic procedure which combines the 
Szekeres-Wilf and Brelaz ooloring procedures is presented at the end. 
Math.Subj.Glasa.(1980): 05C15 
NEKAJ PRIMEROV PREVEDBE PROBLEMOV NA NALOGO O BARVANJU 
TOČK GRAFA 
Nalogo o barvanju točk grafa zastavimo takole: 
Dan Je graf G = ( V,E ) . Pobarvaj točke grafa G tako, 
da ne bo noben par sosednjih točk pobarvan z isto ba.^vo. 
Običajno zahtevamo še: 
Pri tem uporabi čim manjše število različnih barv. 
Naloga o barvanju točk grafa sodi v seznam "osnovnih" 
(kanonskih) korabinatoričnih nalog, saj lahko nanjo 
prevedemo celo vrsto, navidez neprimerljivih, nalog. 
Poglejmo si nekaj primerov: 
1. Radijski oddajniki 
Radijska oddajnika lahko motita eden drugega, če sta si 
preblizu. Kako razdeliti valovne dolžine dani množici 
oddajnikov, tako da se ne bodo medsebojno motili? Koliko 
najmanj valovnih dolžin je za to potrebnih? 
Prevod: 
TOČKE GRAFA: oddajniki 
POVEZAVE: oddajnika sta sosednja (povezana), če .sta si 
preblizu (lahko motita eden drugega) 
BARVE: valovne dolžine 
2. Turistični vodiči 
Turistična agencija namerava organizirati izletov. Za 
vsak izlet 1 poznamo datum njegovega začetka Z, in 
datum njegovega konca K. . Koliko (najmanj) vodičev je 
potrebnih za Izvedbo teh izletov? Katere Izlete' bo vodil 
posamezni vodič? 
Prevod: 
TOČKE GRAFA: izleti (oziroma skupine, če je za isti izlet 
predvidenih več vodičev) 
POVEZAVE: izlet i Je povezan z izletom j natanko 
takrat, ko je: 
BARVE: vodiči 
( Z. ,K, )/n( Zj .Kj ) i( (8. 
3. Optimizacija porabe pomnilnika 
Naj bo X = i ^iJ množica spremenljivk (istega tipa, da 
ne bo težav), ki nastopajo v nekem programu. Nekaj 
prostora prihranimo, če nekaterim spremenljivkam priredimo 
isti prostor; seveda tako, da dobimo ekvivalenten program. 
Koliko najmanj prostora je potrebnega? Katerim 
spremenljivkam pripada isti prostor? 
Prevod: 
TOČKE GRAFA: spremenljivke 
POVEZAVE: točki sta povezani, če sta ustrezni 
spremenljivki lahko istočasno aktivni 
BARVE: prostor v pomnilniku 
Morda ne bo odveč, če malo natančneje opišemo, kako 
določimo povezanost (Istočasno aktivnost) dveh 
spremenljivk: Sestavimo shemo programa in v njej povsod 
zamenjamo akcije z ustreznimi: 
lise X - vrednost spremenljivke X Je bila uporabljena 
oziroma 
Def X - vrednost spremenljivke X je bila spremenjena 
V pravilno sestavljenem programu moru biti na vsaki poti 
po shemi programa od. začetka do nekega Use X vselej vsaj 
en Def X . TočVi X in Y sta povezani natako takrat, 

36 
ko lahko v shemi programa najdemo pot z začetkom v Del' y 
tn koncem v Use X , ki ne vsebuje nobene točke z oiinako 
Def X . 
4. Smaforjl 
Na danem križišču so predvidene določene smeri vožnje. Na 
primer krliišoe (Ajdovščina v LJubljani): 
d a 
Sestavi režim delovanja semaforjev na križišču (določi 
Istočasne smeri) z najkrajšim ciklusom 
Prevod: 
TOCKE CRAFAi smeri vožnje . 
POVEZAVE: smeri sta. povezani, če se v križišču sekata 
(lahko pride do trčenja) 
BARVEi faze semaforskeBa režima 
V našem primeru dobimo naslednji graf, ki ga lahko 
pobarvamo s štirimi barvami (1,2,3,4): 
In določa naslednji režim: 
BARVANJA TOCK GRAFOV - OSNOVNI POJMI 
Naj bo dan graf G » ( V,E ) , množica barv C In "barva" 
nepobarvano B ^ C . Vpaljlmo še okrajšavo 
^a ' ^ ^{*y •''•'laJ Imenujemo delno barvanje točk grafa 
Q vsako preslikavo 
• c :• V —• C • 
• • "•••,. ••• 
ki zadošča pogoju 
,Vu,v£v : ( (U:V)£E/Vvo(u) = o(v) =^ o(u) = i ), 
Delno tiiirvaiije. Je barvanje natanko takrat, ko Je 
c(V)SC . Torej vsako barvanje zadošča-pogoju 
Vu.v^V : ( (u:v)^E =^ č(u)<c(v) ) 
Posebna primera (delnih) barvanj sta barvanje c , ki J« 
določeno a predpisom c : v I—• a in Injektivno barvanje 
C , ki zadošča pogoju u ^ v s:^ č(u) 4 d(v) . 
V nadaljevanju se bomo omejili na končne grafa - grafe, 
pri katerih sta množica točk V in množica povezav. E 
končni. 
Barvitost delnega barvanja c Imenujemo šte/ilo 
X(G/c) = card( c(V) flc ) 
Graf G Je r-(delno)obarvljiv natanko takrat, ko obstaja 
(delno) barvanje c , tako da Je 'X(G/c)^r . Predvsem 
pa Je v tej zvezi zanimivo število 
X(C) = min X(C/c) 
C Je barvanje 
ki mu pravimo barvnoat grafa O ali tudi kraoatlSno 
število. Rečemo tudi, da Je graf G ^-barven. 
Podobne pojme lahko definiramo tudi za barvanja povezav. 
V tem sestavku se z barvanji povezav ne bomo ukvarjali. 
Posamezni točki v^V grafa O lahko glede na delno 
barvanje c priredimo nekaj karakterističnih množic: 
- ouiožlca barv sosedov točke v 
C(v/c) . [ c(u) : (V:U)€E ] 
Zanjo velja ocena card(C(v/c)) ^d(v) , kjer smo i d(v) 
označili stopnjo (č število sosedov) točke v . 
- množica prostih barv za barvanje točke v glede na., c 
• C(v/c) = C \C(v/c) 
oziroma, če dopuščamo še "barvo!' nepobarvano 
; C^(v/o) = C(v/c) Ui»J 
Točka vč,V grafa je casliena za barvanje o , natanko 
takrat, ko Je 
C(v/c) = [c(v) J 
Barvanje, v katerem so vse točke, zasičene, imenujemo 
zasičeno barvanje, 
- barvni razred barve a£c 
V(a/c) = {včv : o(v) • a J ' 
Očitno Je vsak V(a/c) neodvianamnožica. 
Gornje množice lahko na naraven način posplošimo' na vsi 
elementov. Na primer: i 
V(a,b/c) » V(a/c) (Jv{b/o) 
- Keopejeva komponente grafa G ' za barvi • in b 
imenujemo povezane komponente podgrafa 
( V(a,b/c), E(a,b) ) , 
kjer Je i 
E{a,b) = [ (U:V)£E : { c(u) ,o(v) j . [a,b} J 
Pogosto nas zanima med njimi komponenta, ki vaebuje 
povezavo p(u:v) , seveda za barvi c(u) in c(v) , 
Označimo Jo K(p/č) , oziroma, če hočemo biti določnejši 
K(p;a,b/c) , pri čemer Je a B C(U) in bi o(v) . 
Komponento za barvi ' a In b , ki vsebuje točko v , 
c(v) ca, pa označimo K(vib/o) oziroma daljše 
K(via,b/c). . 
Pravkar definirani pojmi nam omogočajo vpeljati pri dani 
^množici barv C naslednji transformaciji nad barvanji; 

36 
- zamena barve v točki v 
o' C S(via/c) , ačc(v/c) 
Novo barvanje c' Je določano s predpisom 
i) u i v 
(
c(u) 
V primeru, ko dopuščamo, tudi "barvo" nepobarvano, 
aČC (v/o) , pa dobimo močnejšo transformacijo 
c' • s"(v;a/c) 
ki Je definirana s podobnim predpisom kot S . 
- Keopejeva zaaena glede na barvi a in b v komponenti, 
ki vsebuje točko v , c(v) s a : 
o' • I(via,b/c) 
Novo barvanje c' je določeno s predpisom: 
c(u)sb Au^K(via,b/o) 
c'(u) 
r a c(u)sb AufcK(vi 
I b c(u)«a Au£K(vi 
(_ o(u) u^K(v;a,b/c) 
ia,b/o) 
Ker nas oznake barv ne zanimajo, je smiselno Izbrati nek 
standardni nabor barv. Pri kortčnih grafih lahko Izberemo 
na primer CCN ; oziroma, če želimo Izbor barv še bolj 
omejiti, postavimo za množico barv C c j[l..n^. 
Naj bo C C -barvanje grafa G . Poglejmo si pobliže 
postopek; 
uhlle ^v : c(v)> min C(v/c) do 
C :» S(vjmin C(v/c) / o); 
Vpeljimo funkcijo 
C)(c) = ^^clv) . 
Za vrednosti funkcije O* velja ocena Qi't.c)^p , kjer 
Je pa cBrd(V) . Ker se na vsakem koraku postopka 
vrednost 0'(c) zmanjša, se mora postopek v končno 
korakih Izteči. Dobljeno končno barvanje označimo s c . 
in mu pravimo reducirano barvanje. 
Danemu barvanju c v splošnem pripada več reduciranlh 
barvanj (odvisnih od zaporedja redukcij). Za vsa pa velja 
ocena X(G/c^^j)^ V(C/c) in naslednja lastnost 
VvčV,Vk€0.-c^ed<*J-0.3"^V = 
( (u:v)ČE Ac^^^(u)«k ) 
Torej je c^^^ arundyeva funkcija grafa G . 
Is Jautnoatl (2') dobimo takoj oceno; 
(IJ) cJ(C) ^ 'X(G) 
kjer Je «c3(G) moč največjega skupka (klike, polnega 
podgrafa) grafa G . 
Enakost v oceni (5) velja na primer za polni graf 
a)(K ) = X(K ) s n . Po drugi strani pa Je Tutte pokazal, 
da obstajajo grafi z oJCO = 2 In poljubno velikim 
X(G) . Se močnejši Je Erdos-Lovaszev izrek, ki pravi, da 
za vsak par naravnih števil m in n obstaja n-barven 
graf, v katerem dolžina najkrajšega cikla presega m . 
Zanimivo oceno barvnostl grafa G nam daje tudi naslednji 
Izrek (Roy, Callal); 
Naj bo G' = ( V, A(E) ) usmerjeni graf, ki ga dobimo 
tako, da poljubno usmerimo povezave grafa G c ( V, E ) 
in naj bo m dolžina najdaljšega enostavnega sprehoda po 
G' , potem je 
X(G) ^ m + 1 
Konlgov Izrek pa pravi: 
0((C)^Z natanko takrat, ko je G dvodelen graf. 
Leta 1976 sta K. Appel in W. Haken, s pomočjo računalnika, 
pozitivno odgovorila na več kot sto let stari probla« 
itlrih barv: vsak ravninski graf Je mogoče pobarvati z 
največ štirimi barvami. Za orlentabllne ploskve višjih 
redov so Heaviood (1890), Heffter (1891), Ringel In Youngs 
(1968) pokazali,, da Je vsak graf, ki ga lahko vložimo v 
orientabllno ploskev reda n O , mogoče pobarvati z 
največ 
L(7 • h + ta.n ) / sj 
barvami. 
Zanimivi sta tudi zvezi med barvnostjo grafa G in 
njegovega komplementa C , ki sta Ju našla Nordhaus in 
Gaddum: 
l_2 yrj^X(G) + 'X(Q) ^ p • 1 
p ^X(G).X(a) ^f((p • i)/2)^] 
kjer Je p = card(V) . 
Omenimo še znani Brooksov izrek: 
V povezanem nepolnem grafu G z i!!\(G).^3 velja 
Dokaze naštetih izrekov in še nekaj drugih rezultatov 
najdete v (Batagelj, 1980). 
BARVN03T GRAFA - LASTNOSTI tN OCENE 
Neposredno iz definicije barvnostl X(G) grafa G 
razberemo naslednje lastnosti: 
(O >'(C) ^ X(G/c) S^card(V) 
(2) HSG =^ X(H/c):ž'X(G/c) 
(3) naj bodo G, komponente povezanosti grafa G , potem 
je 
"Kla/c) z max X(Gj/c) 
(t) 'X(C) ^ AtO) + ' . kjer Je A(G) = max d(v) 
v£V 
če v (2) in (3) postavimo namesto o barvanje c"*^ 
/CiO/c P ) - X(Q) . dobimo, po krajšem razmisleku 
(2-) HSG => 'Xm ^ X(G) 
(3') OdO) = raax X("^) 
ALGORITMI ZA BARVANJE GRAFOV 
Raziskave na področju zahtevnosti algoritmov so pokazale, 
da sodi problem barvanja točk grafa med NP-polne probleme 
(Karp 1972, Aho, Hopcroft, Ullraan 1971). Zato najbrž ne 
obstaja polinomsko omejen postopek za reševanje tega 
problema - vsi postopki, ki zagotavljajo minimalno 
barvanje; zahtevajo v najslabših primerih prebor skoraj 
vseh možnih barvanj in so pomemtakem reda p I . 
Iz literature so znani postopki "usmerjenega" prebora, ki 
z domiselnim odmetavanjem neperspektivnih delnih barvanj 
lahko ponavadi v zmernem času (do 1000 s na računalniku, 
kot Je CIBEH) določijo minimalna barvanja grafov a tja do 
100 točkami. Za najuspešnejše med njlral so se izkazale 
izpeljanke naslednje zamisli, ki Jo Je že Jeta 191(9 
uporabil Zykov v zve/.l s kromatlčnlml polinomi; 

37 
Vzemimo v grafu, ki ga želimo pobarvati poljubni 
nepovezani to£kl. Nastopita dve možnosti 
- to2kl sta v (minimalnem) barvanju enako pobarvani; 
- tpikl ata v (minimalnem) barvanju različno pobarvani. 
Oba možnosti lahko popišemo z ustreznima transformacijama 
osnovnega grafa: 
- 2e ata to£kl enako pobarvani, Ju združimo v eno 
(Identificiramo)I 
- ia sta točki različno pobarvani, Ju povežemo s povezavo. 
Tako dobimo, drevo, katerega točke so grafi, listi pa polni 
grafi. Stopnja polnega grafa - lista Je enaka Številu barv 
v barvanju, ki ga določa pot po drevesu od vrha do lista. 
Posamezni postopki se razlikujejo v naČlnu pregledovanja 
tega drevesa In v pravilih odmetavanja neperspektivnih 
vej. / 
Za zelo učinkoviti sta se Izkazali naslednji, sicer 
preprosti, Hedetniemijevl pravili: 
Pl. če v grafu obstaja točka u , ki Je povezana z vsemi 
ostalimi (po povezavi), potem ^o v vsakem barvanju točka 
u imela barvo drugačno od vseh drugih točk. 
P2. če v grafu obstajata točki u In v , taki da si 
val sosedi točke u tudi sosedi točke v , potem uostaja 
Dlnlmalno barvanje grafa, v katerem sta obe točki, enako 
pobarvani. 
Obe pravili omogočata, da točko u "izločimo" iz grafa -
nadaljnjega pregledovanja. 
Nekoliko drugačen pristop Je ubral Chrlstofldes, ki Je 
pokazal, da Je ^-barven graf mogoče pobarvati s X 
barvami tako, da najprej pobarvamo maksimalno neodvisno 
množico V > N(a) s prvo barvo, nato z drugo barvo 
pobarvamo maksimalno neodvisno množico V, s N(G(VSV,)) , 
... Seveda moramo tudi tu pregledati vse možne maksimalne 
neodvisne množice. 
Podrobneje so tovrstni algoritmi opisani v (Godec, 1983). 
Kaj pa, če Je graf prevelik ali pa Je cena za iskanje 
ninimalnega barvanja s postopkom prebpra prevelika? Tedaj 
se moramo zateči k hevrlstlčnlm postopkom barvanja in se 
e tem odpovedati zagotovilu, da je dobljeno barvanje 
minlmalndi čeprav lahko slednje včasih pokažemo, tako da 
najdemo polni podgraf na )((Q) točkah. 
Stvar Je ie hujSa. Garey In Johnson (1976) sta pokazala 
naslednje: Naj A(a) označuje IteVllo barv, s katerimi 
pobarva postopek A dani graf G . Potem najbrž (zaradi 
NP-polnostl) ne obstaja pollnomsko omejeni postopek, ki 
bi zagotavljal, da Je 
A(G) / 7C(G) < r < 2 
Trenutno nista znana nobena konstanta r^O in 
pollnomsko omejeni postopek A , za katera bi veljalo 
• A(a) / X(0) < <• 
Najboljia meja Je reda p / log p . 
Večina hevrističnih postopkov za barvanje . točk , grafa 
zadoJča shemi postopkov zaporednega barvanja: 
o :a o 
uhlla 3v : c(v) • • do 
izberi barvo ačc(v/c) 
o :» S(via/c) 
Zato, da bi opisani postopek vedno tekel, mora biti 
vseskozi C(v/o) ^ O . Za to zadostuje, če Je 
caru(C) = AW + 1 . 
Postopki zaporednega barvanja se' med seboj razlikujejo po 
pravilu izbire naslednjega kandidata za barvanje in po 
načinu Izbire barve, s katero ga pobarvamo. 
Preden nadaljujemo omenimo "v tolažbo In vzpodbudo"'nekaj 
verjetnostnih rezultatov o postopkih zaporednega barvanja 
(Erdb°s, Grlmmett, HcDlarmld); . 
Naj bo G(n,p) slučajni graf na n točkah, v katerem 
nastopa posamezna povezava z verjetnostjo p . S X(n,p) 
in 2''(n>P) PB označimo slučajni spremenljivki la 
barvnost oziroma število barv dobljenih z. zaporednim' 
barvanjem grafa G(n,p) . Tedaj veljata skoraj za vsak 
graf oceni: 
X(n,p) >(1 -£ ) 5 log^ q'' 
in 
T^, (n.p) i^ (1 *£) n.logjj q" 
• 1 
kjer je qi1-p, p * \ in £>Q . 
Iz zgornjega razberemo, da velja 
'Z?(n.p) /X(n.P) < 2 •£ 
Torej zaporedna barvanja v povprečju le niso teko slaba. 
Povrnimo se k postopkom zaporednega barvanja. Kako lahko 
izberemo prosto barvo? Običajno ne razmetavamo z barvami 
in Jih zato raje po potrebi dodajamo. Torej; 
- če za dano točko obstaja prosta barva, izberemo eno Izmed 
njih: najmanjšo, kar da reducirano barvanje) ali slučajno, 
kar omogoča večkratno poskušanje; ali pa najmanjkrat 
uporabljeno, kar da razmeroma enakomerno pobarvan graf) 
- če Ima točka sosede vseh dotedaj uporabljenih barv, 
dopolnimo množico barv z novo barvo. Včasih se temu lahko 
izognemo,.tako da s Kempejevlml zamenami sprostimo neko 
barvo na sosedih dane točke. 
Vsakemu zaporednemu barvanju ustreza zaporedje izbir točk, 
ki popisuje vrstni red barvanja. To zaporedje Je v bistvu 
permutacija točk. 
Za vsak graf G obstaja taka permutacija točk OT , da 
da zaporedno barvanje točk v zaporedju, ki ga določa 
<jl' , pri čemer vselej izbiramo najmanjšo prosto barvo, 
minimalno barvanje grafa O . V to se prepričamo takole: 
Naj bo C reducirano minimalno barvanje grafa O . 
Uredimo' točke grafa po naraščajočih vrednostih 
pripadajočih barv. Dobljeno zaporedje točk določa iskano 
permutaoijo IJT . 
Torej Je osnovno vprašanje pri zaporednih postopkih 
barvanja: Kako najti "ta pravo" permutaoijo - določiti 
pravi vratni red barvanja? 
Poglejmo si nekaj možnosti: 
Welah-Fouallov postopek: temelji na naslednjem receptu: 
permutacija %" Je določena s padajočim vrstnim redom 
stopenj dj točk grafa G . Za WP-postopek Je mogoča 
pokazati oceno: 
Naj bo d^,^ dj >d, ... ?» d padajoče zaporedje stopenj 
točk grafa G , potem je 
X(0) «^ WP(G) < max { 1 : i < dj • 1 J 
Drevesni postopki: temelje na drevesnih permutacljah: 
permutacija X Je drevesna natanko takrat, ko za vsak 
i^O-.lO velja: 
{u : (V^:U)£EJ f) {v^ : k^Ov-l-Oi * » 
TI postopki Imajo naslednjo lepo lastnost 

Drevesni zaporedni poatopkl barvanja se ekaaktni za 
dvodelne grafe. 
Primer drevesnega postopka je Brelazov postopek. Tu Je 
pernutaclja V takole doloSona: 
vae točke imajo vrednost O i 
toSkl. M ima najvežjo otopnjo, postavi vrednost na 1 
far i o 1,2, ... ,p do 
•}r<l) " točka t največjo vrednostjo, ki še nI v ST 
vaem aosedom točke TTd) povečaj vrednost za 1 
V Bralazov postopek Je v bistvu vgrajena ideja takojšnjega 
barvanja polii(eJš)lh pografov. 
Szebera-Ullfov postopek: je stranski produkt pri izpeljavi 
naslednje ocene za barvnost grafa: 
Naj preallkava f : C- —*« R zadošča pogojema: 
(1) H ^0 =:$> r(H) < f(C) 
(2) f (G) ^ ^mtn d(v) 
v^VfO^ 
potem volja 
X(G) < f(C) + 1 
Ena izmed funkcij f , ki zadoščajo pogojema (1) in (2) 
je f(G> a mBX A(a) - največja lastna vrednost grafa. 
Szekeres In Wllf pa sta pokazala 5e: 
Najmanjša funkcija, ki zadošča pogojema (1) in (2) je 
f„(G) o max raln d„(v) 
° HSG v£V(H) " 
Označimo SU(G) s f^CG) * 1 
Ker Je vedno SW(G} ^ WP(G) , nima smisla programirati 
WP-postopk8. Tako nam ostaneta na izbiro še SW-po8topek 
in Brelazov postopek. Izkaže se, da Ju lahko združimo v 
enoten postopek odvisen od dveh parametrov r in s : 
določi stopnje točk iiC\l i v^V ; 
8W :» min {dOil ' "Ojl 
val :ii O ; W :° V j 
for i :o 1 to p do 
v :B ergmtn{d[><] t HČwJ} 
if <i[y'2 > aw then 
val tu val '» r I su :> d[w]I 
•ndif ! 
d°tv3 :« vel i W :a WS {v} ( 
for U€EXT(STAR(V)) n« <lo 
d[u2 :» d[ul - 1 
endfor 
andror ; 
W t. V 1 
for i :s 1 to p do 
v :o ergraaxjd [vj : WCHJ | 
ool[yJ ;a selectcolor j 
W := WS£vS i 
for U£EXT(STAR(V)) nw do 
d'M :. d^Cu] • a 
andfor 
sndfop ) 
Gornji postopek nam pri r • O in s / O da Brelazov 
postopek; pri r ^ O in s •> O pa SW-po8topek| zanimive 
pa so tUdI njun» kombinacije pri neničelnih r in s , 
Postopek učinkovito sprogramlramo tako, da organiziramo 
d in d" v kopico (lahko celo isto). 
Ka računalniku DEC-10, Univerze v Ljubljani Je postopek 
vgrajen v program COLORS programskega paketa za delo z 
grafi GRAPH. Program COLORS v zmernem času določi dobra 
barvanja grafov ne do tisoč točkah in nekaj tisoč 
povezavami. 
LITERATURA 
fllAho A.V., Hopcroft J.E., Ullman J.D.: The design and 
Bnalysls of computer algorlthos. Addlson Wesley, Raading, 
Mass. 197'* 
f2] Batagelj V.: Barvanja točk grafov. Seminar ca 
numerično in računalniško matematiko IMFH-201, LJubljana, 
november 1960 
[3] Berge C: Oraphes et Hypergraphea (2. ed.), Ounod, 
Pariš 1973 
£4] Brelaz D.: New methods to color the vertices of a 
graph. CACM, 22(1979)1), 251-256. 
[5] Carr^ B.: Graphs and netvorka. Clarendon Presa, Oxrord 
1979. 
[6] Catlln R.A.: Brooks' graph-colorlng theorem and the 
independence number. J, of comb. Theory, seriea B, 
27(1979), «2-48. 
[l^ Chrlstofldes N.: An algorlthis for the ohromatic nunbar 
of a graph. The Computer Journal, 11(1971), 38-39. 
£ 8] Cole A.J.: The preparation of examinatlon tloe-tables 
uslng a small-store computer. The Computer Journal, 
7(1964), 117-121. 
[9] Cornell D.C., Graham B.i An algorlthm for determlning 
the chromatlc number of a graph. SIAM J. Comput., 2(1973), 
311-318. 
[10J Cvetkovič D., Mlllč M.: Teorija grafova 1 njen« 
primene. NauSna knjiga, Beograd 1977. 
|jl] Demlng R.W.: Acycllc orlentatlona of a graph and 
chromatlc and independence numbers. J. of Conb. Theory, 
serles B, 26(1979), 101-110. 
[12] Garey M.R., Johnson D.S.: The coaplexlty of near-
optimal graph colorlng. JACM, 23(1976), 43-49. 
[13] GRAPH - programi. Priročnik za DEC-10, LJubljana, 
1982. 
[14] Graver J.E., Matklns H.E.: Combinatorics ulth emphaais 
on the theory of graphs, Sprlnger-Verlag, Ne« Ifork 1977. 
[15] Godec H.; Algoritmi za barvanje grafov. FNT, 
matematika, diplomsko delo 279, Ljubljana 1983. 
[l6l Grlmmett G.R., HcDlarmld C.J.H.: On colourlng random 
graphs. Math.Proc. Carab. Phll. Soc, 77(1975), 313-324. 
fn] Harary F.: Graph theory. Addlson-We8ley, Readlng, 
Hass. 1969. 
[18] Hedetnierai S.T.: Review no. 22063. Comput. Rev. 
12(1971), 446-447. 
Q93 Karp R.H.: Reduclblllty among comblnatorial problema 
(Complexity of Computer Computations, Miller R.E., 
Thatoher J.W., Ed.). Plenura Press, Wew Kork 1972, 85-103. 
120^ Karp R.M.: The probablllatlo analy8l8 of some 
combinatorial search algorlthms (Algorithns and 
Complexity, Traub J.F., Ed.). Academlo Preas, N«w York 
1976, 1-19. 
[21I Matula D., Harble G., laaacson J.: Graph colorlng 
algorlthms (Graph Theory and Computlng, Read R.C., Ed.), 
Academlc Press, New Hork 1972, 109-122. 
[22] HcDlarmld C.J.H.; Colouring random grapha badly. 
(fotokopija iz neznanega zbornika). 
[233 Melnikov L.S., Vlzlng V.G.: New proof of Brooks' 
theorem. J. of Comb. Theory, 7(1969), 289-290. 
£24] Nljenhuis A., Wllf H.S.: Combinatorial algorlthms (2. 
ed.). Academlc Press, New Vork 1978. 
[25] Ore O.: The four color problem. Academlo Presa, New 
Kork 1967. 
{263 Peršin O.Ju.: Algorltm opredelenlja minlmalnoj 
raskraski konečnogo grafa. Izvestija akademll nauk SSSR, 
Tehnlčeskaja klbernetika, (1973)6, 114-119. 
(27"] Szekeres G., Wlir H.S.; An lnequallty for the 
chromatlc number of a graph. J. of Comb. Theory, 4(1968), 
1-3. 
[28] Welsh D.J.A., Powell H.B.: An upper bound for the 
chromatlc number of a graph and tts applicatlon to 
tlmetabllng problema. The Computer Journal, 10(1967), 
85-86.