Bojenje grana grafa

U oblasti teorija grafova, bojenje grana grafa je dodeljivanje boja, granama grafa tako da dve susedne grane nemaju istu boju. Na primer, slika sa desne strane pokazuje bojenje grana grafa žutom, zelenom i crvenom bojom. Bojenje grana je jedno od nekoliko različitih tipova bojenja grafova. Problem bojenja grana postavlja pitanje da li je moguće obojiti grane datog grafa koristeći najviše к različitih boja, za zadanu vrednost к, ili sa najmanje moguće boja. Minimalan broj potrebnih boja za grane datog grafa naziva se hromatski indeks grafa. Na primer, grane grafa sa slike mogu biti obojene sa tri boje ali ne mogu biti obojene sa dve, dakle dati graf ima hromatski broj tri.

Bojenje grana sa 3 boje Desagruevsovog grafa

Po Vizingovoj teoremi, broj potrebnih boja da bi se obojile grane prostog grafa je ili njegov maksimalni stepen Δ ili Δ+1. Za neke grafove, kao što su bipartitni grafovi i visoko stepeni planarni grafovi, broj boja je uvek Δ, a za multigrafove, broj boja može biti čak i 3Δ/2. Postoje algoritmi polimijalne vremenske složenosti koji računaju optimalno bojenje bipartitnih grafova, i bojenje nebipartitnih prostih grafova koji koriste najviše Δ+1 boja; ipak, opšti problem pronalaženja optimalnog bojenja grana je NP-kompletan i najbržim znanim algoritmima za to je neophodno eksponencijalno vreme. Proučavane su mnoge varijacije problema bojenja grana, u kojima dodeljivanje boja grana mora zadovoljiti i druge uslove, a ne samo uslov o susednim granama. Bojenje grana ima primenu u problemima raspoređivanja i u dodeljivanju frekvencije za optičko vlakno mreže.

Primeri

Ciklični graf može imati grane obojene sa dve boje, ako je dužina ciklusa parna: naizmeničnim menjanjem boja u ciklusu. Ali ako je dužina neparna, potrebne su tri boje.

Geometrijska konstrukcija bojenja grana kompletnog grafa K₈ sa 7 boja. Svaka od sedam boja ima jednu granu od centra do čvora poligona i tri grane normalne na njih.

Kompletan graf Кn sa n čvorova može imati grane obojene sa n − 1 bojom, kada je n paran broj; ovo je poseban slučaj Baraniaiove teoreme. Soifer 2008 dokazuje sledeću geometrijsku konstrukciju bojenja u ovom slučaju: postaviti n pokazivača na temena i centar regularnog n − 1 jednostranog poligona. Za svaku klasu boje, treba uključiti jednu granu od centra do jednog od temena poligona, i sve normalne grane koje povezuju parove temena poligona. Ipak kada je n neparan, potrebno je n boja: svaka boja može biti upotrebljena za (n − 1)/2 grana, a 1/n-ti deo od ukupnog broja.

Nekoliko autora je proučavalo bojenje grana neparnih grafova, n-regularnih grafova u kojima čvorovi predstavljaju timove sa n − 1 igrača izabranih iz skupa od 2n − 1 igrača, i u kojima grane predstavljaju moguća uparenja ovih timova (sa jednim igračem ostavljenim kao "neparan čovek napolju" da sudi). Slučaj u kome je n = 3 daje dobro poznat Pitersonov graf. Kao što Biggs 1972 objašnjava problem (za n = 6), igrači žele da nađu raspored za oba uparenja tako da svaki tim igra svaku od svojih 6 utakmica različitim danima u nedelji, sa nedeljom kao slobodnim danom; tj, matematički formulišući problem, oni žele da nađu 6 regularnih neparnih grafova O₆ sa granama obojenim sa 6 boja. Kada je n jednako 3,4 ili 8, bojenje grana O_n zahteva n + 1 boju, ali kada je 5, 6, ili 7 potrebno je samo n boja.

Definicije

Kao kod bojenja čvorova grafa, bojenje grana grafa, kada nije drugačije naglašeno, podrazumeva da uvek bude pravilno bojenje grana, što znači da se dvema susednim granam ne sme dodeliti ista boja. Smatra se da su dve grane susedne kada imaju zajednički čvor. Bojenja grana grafa G može se posmatrati kao bojenje čvorova linijskog grafa L(G), grafa koji ima čvor za svaku granu grafa G i granu za svaki par susednih grana iz grafa G.

Pravilno bojenje grana sa k različitih boja se zove (pravilno) k-bojenje grana. Za graf koji ima svojstvo (pravilnog) k-bojenja grana, kaže se da može biti k-obojiv. Najmanji broj boja potrebnih u (pravilnom) bojenju grana grafa G je hromatski indeks, ili hromatski broj grana χ′(G). Hromatski indeks je takođe ponekad zapisan u notaciji χ₁(G); u ovoj notaciji indeks (potpisani znak) 1 ukazuje da su grane jednodimenzioni objekti. Graf je k-hromatski ako je hromatski indeks tačno k. Hromatski indeks ne treba mešati sa hromatskim brojem χ(G) ili χ₀(G), minimalnim brojem boja potrebnih za pravilno bojenje čvorova grafa G.

Ukoliko se ne kaže drugačije, pretpostavlja se da su svi grafovi prosti, za razliku od multigrafa u kojima dve ili više grana mogu povezivati isti par čvorova i u kojima može biti petlja sa samim sobom (jednim čvorom). Za mnoge probleme u bojenju grana, prosti grafovi se ponašaju drugačije od multigrafova, pa je neophodan dodatni napor da bi se proširile teoreme vezane za bojenje grana prostih grafova na slučaj multigrafa.

Veze sa uklapanjem

Ovaj 3-regularan planarni graf ima 16 temena i 24 grane, ali samo 7 grana je u maksimalnom podudaranju. Zbog toga zahteva 4 boje prilikom bojenja grana.

Podudaranje u grafu 'G' je skup grana, tako da nikoje dve nisu obojene istom bojom; savršeno podudarenje je podudaranje koje uključuje ivice koje dotiču sve čvorove grafa, i maksimalno podudaranje je podudaranje gde se uključuje što je više moguće grana. U bojenju grafa, skup grana sa jednom od boja moraju da budu nesusedne tako da formiraju podudaranje. Bojenje grana grafa je isto kao i podela grafa na disjunktne podgrafe.

Ako je broj maksimalnih podudaranja u grafu mala, onda će biti potrebno puno uparivanja da bi se pokrile sve grane grafa. Formalnije rečeno, ako graf ima m grana, i ako najviše β grana pripadaju maksimalnom podudaranju onda u svakom bojenju grafa se mora koristiti najmanje m/β različitih boja. Na primer, 16-vertex planaran graf prikazan u ilistraciji ima m = 24 ivica. U ovom grafu se ne može naći savršeno uparivanje; za, ako je na srednjem delu izvršeno podudaranje, preostale neuparene čvorove mogu da se grupišu u tri, različito povezane komponente sa četiri ili pet čvorova i komponente sa neparnim brojem čvorova ne mogu imati savršena podudaravanja. Međutim graf ima maksimalno podudaranje sa sedam grana tako da je β = 7. Tako je broj boja potrebnih za bojenje grafa najmanje 24/7 i kako taj broj mora biti ceo broj, znači najmanje četiri.

Za regularan graf stepana k} koji nema savršeno podudarenje, donja granica može da bude barem k + 1 potrebnih boja. Naročito je ovo tačno za regularan graf sa neparnim brojem čvorova (kao što su neparni kompletni grafovi); za ovakve grafove, preko lema o rukovanju, k mora da bude parno. Međutim, nejednakost χ′ ≥ m/β ne objašnjava u potpunosti hromatski indeks u svakom regularnom grafu, zato što postoje regularni grafovi koji imaju savršeno poklapanje, ali nisu k-obojivi. Na primer, Pitersonov graf je regularan, sa m = 15 i β = 5 grana u savršenom podudaranju, ali nema 3-bojenje.

Veze sa stepenom

Vizingova teorema

Granični hromatski broj grafa G je veoma tesno vezan sa maksimalnim stepenom Δ(G), najvećim brojem grana incidentnih svakom čvoru G. Očigledno χ′(G) ≥ Δ(G), ako se Δ različitih grana stapaju u čvor V i sve ove grane moraju biti druge boje od ostalih koje se stapaju u taj čvor, a to može biti moguće samo ako ima najmanje Δ boja na raspolaganju. Vizingova teorema(po Vadim G. Vizing koji je objavio ovo 1964) tvrdi da je ova veza jako uska za svaki graf granični hromatski broj je ili Δ(G) ili Δ(G) + 1.

Kada je χ′(G) = Δ(G), kaže da je u klasi 1, inače je u klasi 2.

Svaki bipartitan graf je klase 1, i skoro svi ostali grafovi su klase 1. Međutim problem je NP-kompletan za određivanje da li je proizvoljni graf klase 1.

Vizing 1965 je dokazao da planarani grafovi maksimalnog stepena od najmanje osam su klase 1 I istovremeno da su takvi i planarni grafovi maskimalnog stepena sedam ili šest. S druge strane postoje planarni grafovi maskimalnog stepena od dva do pet, koji su klase dva. Ovo je dokazano za grafove maskimalnog stepena sedam. Nepovezani planarni kubni grafovi su svi klase 1; ovo je ekvivalentna forma 4 boja teoreme.

Regularni grafovi

1-faktorizacija "k"-regularnog grafa, podgraf sa granama grafa u savršenom poklapanju je isto kao i "k"-bojenje grana grafa. Regularni graf ima faktorizaciju jedan i to samo ako je klase jedan. Specijalan slučaj ovoga je 3-bojenje kubnog grafa(3-regularno) i još ponekad nazivan Tait bojenje.

Nema svaki regularni graf faktorizaciju jedan, na primer Pitersonov graf nema. U generalnom slučaju 'snarkovi' su definisani kao grafovi koji, kao Pitersonov graf, su nepovezani 3-regularni klase dva.

Prema Kőnig 1916 svaki bipartitni regularni graf ima jedan faktorizaciju. Ta teorema je izneta ranije u smislu "projektivnih konfiguracija" i dokazana je od strane Ernst Steinitz.

Multigrafovi

Shannon multigraph stepena 6, stepen grananja 3, potrebno 9 boja

Za multigrafove kod kojih različite paralelne grane mogu povezati ista dva čvora rezultat je sličan, ali lošiji nego kod Vizing's theorem u smislu graničnog hromatskog broja χ′(G), maskimalnog stepena Δ(G), i stepena grananja μ(G) i maskimalnog broja grana u bilo kojoj grupi paralelnih grana. Kao prost primer koji pokazuje da Vizing's theorem ne generalizuje se na multigrafove uzimamo u razmatranje Shannon multigraph, multigraf sa tri čvora i tri grupe po μ(G), paralelnih grana koje povezuju svaki od tri čvora. U ovom primeru Δ(G) = 2μ(G), (svaki čvor je incidentan sa samo dve od tri grupe od po μ(G) paralelnih grana), ali je granični hromatski broj 3μ(G)(ima tri 3μ(G) grana ukupno, svake dve su susedne tako da sve grane moraju imati različitu boju u odnosu na ostale). U rezultatu koji je inspirisala Vizing-a, pokazalo se da je ovo najgori slučaj : χ′(G) ≤ (3/2)Δ(G)  za svaki multigraf G. Dodatno za svaki multigraf G, χ′(G) ≤ Δ(G) + μ(G), nejednačina koja se svodi na Vizing's theorem u slučaju prostih grafova(za koji je μ(G) = 1).

Algoritmi

Usled toga što je problem testiranja da li je graf klase 1 NP-kompletan nema poznatog algoritma u polinomijalnom vremene zavisnosti za bojenje grana bilo kog grafa sa optimalnim brojem boja.

U svakom slučaju jedan broj algoritama je razvijen koji reklasiraju jedan ili više kriterijuma: oni jedino rade na podskupu grafova ili ne uzimaju uvek optimalan broj boja ili se ne izvršavaju uvek u vremenu polinomijalne zavisnosti.

Optimalno bojenje specijalnih klasa grafova

U slučaju bipartitnivnih grafova ili multigrafova maksimalnog stepena Δ, optimalan broj boja je tačno Δ. Cole, Ost & Schirra 2001 su pokazali da se optimalno bojenje grafa može uraditi u približno vremenu linearne zavisnosti O(m log Δ), gde je м broj grana grafa; prostije ali sporiji algoritmi su opisani od strane Cole & Hopcroft 1982 i Alon 2003. Algoritam Alon 2003 počinje tako što od ulaznog grafa pravi regularni bez uvećanja njegovog stepena ili značajnog uvećanja njegove veličine, tako što spaja parove čvorova koji pripadaju istoj strain bipartitivnog grafa i onda dodaje mali broj čvorova i grana. Zatim ako je stepen neparan Alon 2003 nalazi jedno savršeno spajanje u vremenu približno linearne zavisnosti, dodeljuje mu boju i uklanja ga iz grafa, što za posledicu ima da stepen grafa postaje paran. Konačno Alon 2003 primenjuje Gabow 1976 opservaciju da biranjem različitih podskupova grana u Ojlerovom putu graf se razdvaja na dva regularna podgrafa, da bi podelio zadatak bojenja grana na dva manja podzadatka i onda se njegov algoritam izvršava rekurzivno na ta dva. Totalna složenost je O(m log m).

Za planarne grafove sa maksimalnim stepenom većim od sedam optimalni broj boja je tačno Δ ≥ 7.

Uz pretpostavku da je Δ ≥ 9, moguće je naći optimalno bojenje grana u vremenu linearne zavisnosti Cole & Kowalik 2008.

Algoritmi koji koriste više od optimalnog broja boja

Misra & Gries 1992 i Gabow et al. 1985 opisali su algoritam polinomijalne vremenske složenosti za bojenje bilo kog grafa sa Δ + 1  boja, vezujući se za Vizing's theorem; Misra & Gries bojenja grana grafa algoritam.

Za multigrafove Karloff & Shmoys 1987 su prezentovali algoritam koji se pripisuje Eli Upfal. Napravite ulazni multigraf G Ojlerov dodavanjem novog čvora koji povezuje granu svakog čvora neparnog stepena, naći Ojlerovu putanju i izabrati usmerenje za putanju. Formirati bipartitan graf Hu kom postoje dve kopije svakog čvora grafa G, jedan sa svake strane bipartacije, sa granom od čvora u na levoj strani bipartitacije do čvora v na desnoj strani bipartitacije, kad god postoji usmerena putanja od čvora u do v u grafu G. Primeniti na bipartitivnom grafu algoritam za bojenje grana na H. Svaka klasa boja u H odgovara skupu ivica u G koji prave podgraf sa maksimalnim stepenom dva; ovo je disjunktna unija putanja i ciklusa, pa tako za svaku klasu boja u H moguće je formirati tri klase boja u G. Vreme algoritma je povezano sa bojenjem grana bipartitivnog grafa,  O(m log Δ) koristeći algoritam Cole, Ost & Schirra 2001. Broja boja koje ovaj algoritam koristi je najvše $3\left\lceil {\frac {\Delta }{2}}\right\rceil$ blizu, ali ne sasvim jednako sa Shannon-ovom vezom od $\left\lfloor {\frac {3\Delta }{2}}\right\rfloor$ . Takođe se može iskoristiti i parelelni algoritam u istom smeru na isti način. Na istom papiru Karloff i Shmoys takođe su predstavili algoritam u linearnoj vremenskoj složenosti za bojenje multigrafova sa maksimalnim stepenom tri, sa četiri boje(koristeći veze između Shannon i Vizing) koji rade na istom principu: njihov algoritam dodaje novi čvor da bi napravili Ojlerov, nalaze Ojlerovu putanju i onda biraju alternativan skup grana na toj putanji da bi podelili graf u dva podgrafa maksimalnog stepena dva. Putanje, čak i ciklusi od svakog podgrafa mogu biti obojeni sa po dve boje po podgrafu. Nakon ovog koraka, svaka naredna neparna petlja sadrži bar jednu granu koja može biti obojena sa jednom ili dve boje koje pripadaju suprotnom podgrafu. Eliminisanjem ove grane iz neparne petlje ostavlja čvorove povezane i ta grana može biti obojena koristeći dve boje za taj podgraf.

Pohlepni algoritam za bojenje koji razmatra grane grafa ili multigrafa jednu po jednu, dodavanjem svakoj grani, prvu slobodnu boju može ponekad da koristi i 2Δ − 1  boja, što može biti približno dvostruko više nego što je potrebno. Međutim ima svoje prednosti koje se mogu iskoristiti u online algoritmima gde ulazni graf nije poznat; u ovakvom okruženju njegov ‘takmičarska ocena’ je dva i to je optimalno: ni jedan online algoritam ne daje bolje rezultate. Premda ako grane stignu u nasumično izabranom redosledu i ulazni graf ima stepen koji je u najmanju ruku logaritamski, onda manja ‘takmičarska ocena’ može biti dostignuta.

Nekoliko autora je napravilo pretpostavku koja govori da je frakcionalni hromatski indeks bilo kog multigrafa(broj koji se može izračunati u polinomijalnoj vremenskoj složenosti koristeći linearno programiranje) je jedan od hromatskih indeksa. Ako su ove pretpostavke tačne bilo bi moguće da se izračuna broj koji nikada nije veći od jednog od hromatskih indeksa u slučaju multigrafa, podudarajući se sa onim poznatim iz Vizing's theorem za proste grafove. Iako je nedokazana, generalno ove pretpostavke su tačne kada je hromatski indeks barem $\Delta +{\sqrt {\Delta /2}}$, što se može desiti kod multigrafova.

Precizni algoritmi

Jednostavno je proveriti da li je graf obojen sa jednom ili dve boje, tako da je prvi netrivijalan slučaj bojenja grana grafa provera da li je graf obojen sa 3 boje. Kako je Kowalik 2009 pokazao, moguće je testirati da li je graf obojen sa 3 boje u vremenu O(1,344ⁿ), koristeći samo polinomijalan prostor. Iako je vremensko ograničenje eksponencijalno, ovo je značajno brže nego surova (brute force) pretraga kroz sve moguće dodele boja granama. Svaki povezan 3-regularan graf sa n temena ima O(2^n/2) 3-bojenja; sva se mogu izlistati u vremenu O(2^n/2) (malo sporije nego nalaženje jednog bojenja); Kako je Greg Kuperberg primetio, graf prizme nad poligonom sa n/2 stranica ima mnogo bojenja, što pokazuje da je ova veza uska.

Primenom preciznih algoritama za bojenje čvorova linijskog grafa ulaznog grafa, moguće je optimalno obojiti ivice bilo kog grafa sa m grana, bez obzira na broj potrebnih boja, u vremenu 2^mm^O(1) i eksponencijalnom prostoru, ili u vremenu O(2,2461^m) i polinomijalnom prostoru (Björklund, Husfeldt & Koivisto 2009).

S obzirom da je bojenje grana grafa NP-kompletno čak i za tri boje, nije verovatno da će fiksni parametar biti poslušan kada se parametrizuje po broju boja. Međutim, poslušan je za druge parametre. Na primer, Zhou, Nakano & Nishizeki 1996 pokazali su da za graf sa podstablom dubine w, optimalno bojenje grana se može izračunati u vremenu O(nw(6w)^w(w+1)/2), formula supereksponencijalno zavisi od w, ali samo linearno od broja čvorova u grafu n.

Nemhauser & Park 1991 formulisali su problem bojenja grana grafa kao celobrojni program i opisali svoje iskustvo koristeći celobrojno programiranje za rešavanje problema bojenja grana grafa. Međutim, nisu sproveli složeniju analizu svog algoritma.

Dodatne Karakteristike

Jedinstveno 3-obojiv uopšteni Petersenov graf G(9,2). Jedna od tri grupe boja predstavljena je svetlom bojom i druge dve se mogu naći ili rotiranjem svetlih grana za 40° u svakom pravcu ili podelom tamnog Hamiltonovog ciklusa u naizmenične ivice.

Graf je jedinstveno k-ivično-obojiv ako postoji samo jedan način podele grana u k grupa, ignorišući k! mogućih permutacija boja. Za k ≠ 3, jedini jedinstveno k-ivično-obojivi grafovi su putevi, ciklusi i zvezde, ali za {{{1}}} i drugi grafovi mogu da budu jedinstveno 3-ivično-obojivi. Svaki jedinstveno 3-ivično-obojiv graf ima tačno tri Hamiltonova ciklusa (formirani Hamiltonovi ciklusi nisu jedinstveno 3-ivično-obojivi, kao što je Petersenov graf G(6n + 3, 2)) za n ≥ 2. Jedini poznati neplanarni jedinstveno 3-ivično-obojivi graf je generalizovani Petersenov graf G(9, 2), i pretpostavlja se da drugi ne postoje.

Crtanje kompletnog bipartitnog grafa K_3,3 sa svakom od svoje 3 grupe boja nacrtanim paralelno.

Folkman & Fulkerson 1969 istraživali su nerastuće nizove brojeva m₁, m₂, m₃, ... sa osobinom da postoji odgovarajuće bojenje grana datog grafa G sa m₁ grana prve boje, m₂ grana druge boje, i tako dalje. Primetili su da ako je suma niza P izvodljiva u ovom smislu, i ako je leksikografski veći od niza Q sa istom sumom, onda je i Q izvodljiva. Jer, ako je {math|P > Q}} u leksikografskom poretku, onda se P može transformisati u Q nizom koraka, od kojih svaki umanjuje neki od brojeva m_i za jedan i uvećava neki kasniji m_j (i < j) za jedan. U smislu bojenja grana grafa, počevši od bojenja koje predstavlja P, svaki od ovih koraka može se izvršiti zamenom boja i i j na Kempeovom lancu, najduži put grana u kom se smenjuju dve boje. Na primer, svaki graf ima pravilno bojenje grana, bojenje grana sa optimalnim brojem boja u kojoj se veličina svake dve grupe boja razlikuje za najviše jedan.

De Bruijn–Erdős-ова teorema se može iskoristiti za prebacivanje mnogih svojstava bojenja grana konačnih grafova na beskonačne grafove. Na primer, i Šenongova i Vizingova teorema povezuju stepen grafa sa njegovim hromatskim brojem, obe generalizujući direktno na beskonačne grafove.

Richter 2011 razmatra problem nalaženja slike grafa zadatog kubnog grafa sa svojstvima da sve ivice na crtežu imaju jednu od tri različite kosine i da dve ivice ne leže na istoj liniji. Ako takvo grafičko predstavljanje postoji, onda očito te kosine grana mogu da se iskoriste kao boje u 3-ivičnom-bojenju grafa. Na primer, crtanje grafa K_3,3 kao ivice i duže dijagonale pravilnog šestougla predstavlja 3-ivično-bojenje grafa na ovaj način. Kako je Rihter pokazao, 3-pravilni prosti bipartitni graf sa datim bojenjem, ima grafički prikaz ovog tipa koji predstavlja dato bojenje ako i samo ako je graf 3-ivično-povezan. Za nebipartitni graf, uslov je malo komplikovaniji: dato bojenje se može predstaviti grafički ako je dvostruki bipartitni pokrivač grafa 3-ivično-povezan, i ako brisanjem monogromatskog para grana vodi do podgrafa koji i dalje nije bipartitan. Svi ovi uslovi se mogu proveriti u polinomijalnom vremenu; međutim, problem proveravanja da li 4-ivično-obojiv 4-pravilni graf ima grafički prikaz sa granama sa 3 kosine, koji predstavlja boje kao kosine, je ekvivalentan sa problemom ETR, koji je NP-kompletan.

Kao što je povezan sa najvećim stepenom i najvećim sparivanjem grafa, hromatski broj je usko povezan i sa linearnim arbocitetom la(G) grafa G, najmanjim brojem linearnih šuma (razdvojenih grupa puteva) u koje se ivice grafa mogu podeliti. Sparivanje je specijalan slučaj linearne šume, i obrnuto, svaka linearna šuma može biti 2-ivično-obojena, dakle za svaki graf G važi la(G) ≤ χ′(G) ≤ 2 la(G). Akijamina pretpostavka tvrdi da $\mathop {\mathrm {la} } (G)\leq \left\lceil {\frac {\Delta +1}{2}}\right\rceil$, odakle bi sledilo 2 la(G) − 2 ≤ χ′(G) ≤ 2 la(G). Za grafove sa najvećim stepenom 3, la(G) je uvek tačno 2, pa se u tom slučaju veza χ′(G) ≤ 2 la(G) poklapa sa vezom iz Vizingove teoreme.

Drugi tipovi bojenja

Podela kompletnog bipartitnog grafa K_4,4 u tri šume, pokazujući da ima arboricitet tri.

Tuov broj grafa je broj boja potrebnih u bojenju grana grafa da zadovolji uslov da, u svakom putu parne dužine, prva druga polovina puta formiraju različite nizove boja.

Arboricitet grafa je najmanji broj boja neophodnih kako ivice svake boje ne bi formirale ciklus (slično, u običnom bojenju grana, susedne grane ne smeju biti iste boje). Tačnije, to je najmanji broj šuma u koje ivice grafa mogu da budu podeljene. Za razliku od hromatskog broja, arboricitet grafa se može izračunati u polinomijalnom vremenu.

Nizovno bojenje grana je problem u kom je dat graf u kom je svakoj ivici dodeljen niz boja, i treba naći odgovarajuće bojenje grana, tako da boja svake grane bude u njenom nizu. Nizovni hromatski broj grafa G je najmanji broj k takav da, bez obzira kako se biraju nizovi boja za ivice, sve dok svaka grana ima k boja u svom nizu, bojenje je sigurno moguće. Nizovni hromatski broj je uvek veći ili jednak od hromatskog broja. Dinitsova pretpostavka o završetku delimične latinske kocke se može preformulisati kao tvrđenje da je hromatski broj nizovnog bojenja grana kompletnog bipartitnog grafa K_n,n jednak njegovom hromatskom broju grana, n. Galvin 1995 razložio je pretpostavku dokazavši, opštije, da u svakom bipartitnom grafu hromatski broj i nizovni hromatski broj imaju istu vrednost. Pretpostavlja se i da važi jednakost između hromatskog broja i nizovnog hromatskog broj, još opštije, za proizvoljne multigrafove bez samopetlji; ova pretpostavka i dalje nije dokazana.

Mnoge druge često proučavane varijacije bojenja čvorova su takođe prenesene na bojenje grana. Na primer, potpuno bojenje grana je varijanta nekompletnog bojenja, regularno bojenje u kom svaki par boja mora biti predstavljen sa bar jednim parom susednih ivica i u kom je cilj da se postigne najveći broj iskorišćenih boja. Jako bojenje grana je varijanta jakog bojenja, bojenje grana u kom svake 2 grane sa susednim čvorovima moraju imati različitu boju. Jako bojenje grana ima primenu u šemama za dodelu kanala za bežične mreže.

Aciklično bojenje grana je varijanta acikličnog bojenja, bojenje grana u kom svake dve grupe boja formiraju aciklični podgraf (odnosno šumu). Aciklični gromatski broj grafa $G$, označen kao $a'(G)$, je najmanji broj boja potrebnih da bi se dobilo pravilno aciklično bojenje grana grafa $G$. Pretpostavlja se da važi $a'(G)\leq \Delta +2$, gde je $\Delta$ najveći stepen grafa $G$. Trenutno je najbolja veza $a'(G)\leq \lceil 3.74(\Delta -1)\rceil$. Problem postaje jednostavniji kada graf $G$ ima veći obim. Preciznije, postoji konstanta $c$ takva da ako je obim grafa $G$ bar $c\Delta \log \Delta$, onda važi $a'(G)\leq \Delta +2$. Slično važi i za sve $\epsilon >0$, postoji $g$ takvo da ako $G$ ima obim bar $g$, onda važi $a'(G)\leq (1+\epsilon )\Delta$.

Eppstein 2008 je proučavao 3-ivična-bojenja kubnih grafova sa dodatnim svojstvom da dva bihromatska ciklusa ne dele više od jedne zajedničke ivice. Pokazao je da je postojanje takvog bojenja ekvivalentno sa postojanjem grafičkog prikaza grafa na trodimenzionalnom celobrojnom koordinatnom sistemu sa ivicama paralelnim sa koordinatnim osama i svaka paralelna linija sadrži najviše 2 čvora. Ipak, kao i obični problem 3-ivičnnog-bojenja, nalaženje bojenja ovog tipa je NP-kompletno.

Totalno bojenje je bojenje koje kombinuje bojenje čvorova i bojenje grana, koje zahteva da i temena i grane budu obojene. Bilo koji slučajan par grane i temena ili grane i grane, mora imati različite boje, kao i susedna temena. Spekulisano je (kombinacijom Vizing i Brooks' theorem) da bilo koji graf ima totalno bojenje u kom je maksimalan broj boja maksimalan stepen plus dva, ali još uvek nije dokazano.

Ako bi 3-regularni graf na površini je 3-grane-obojen, njegov dualni graf, formira triagulaciju na površini, kom je takođe obojena ivica (ali ipak nije pravilno obojena), na takav način da svaki trougao ima jednu granu od svake boje. Druga bojenja i orijentacije triangulacije, sa drugim lokalnim ograničenjima, kako su boje raspoređene, na temenima ili licima triangulacije, može se koristiti da bi se izlistalo nekoliko tipova geometrijskih objekata. Na primer, pravougona podela (delovi pravougaone podele, na manje pravougaonike gde se svaka tri pravougonika spajaju u jednom temenu), može se opisati kombinatorno uz “regularno obeležavanje”, dvobojno bojenje ivica triangulacionog dela podele, uz graničenje da grane odgovaraju svakom temenu koje formira 4 susedne podele, u kojoj su boje iste.

Ovakvo obeležavanje je paralelno bojenju četvorougaonih podela, u kojima se vertikalne grane boje jednom, a horizontalne drugom bojom. Slična lokalna ograničenja se odnose na raspored u kom obojene grne koje se pojavljuju oko čvora mogu da se koriste da stvaraju pravolinijsku mrežu ugrađujući planarne grafove i trodimenzione poliedre sa paralelnim stranama. Za svaki od ova tri tipa regularnih bojenja, set regularnih bojenja fiksiranih grafova formira distributive lattice koji može da se iskoristi da se brzo izlistaju sve geometrijske strukture zasnovane na samom grafu (kao poliedar sa paralelnim stranama koji ima isti skelet), ili da se nađu strukture koje zadovoljavaju dodatne uslove.

Deterministički konačni automat može biti prikazan kao usmereni graf u kom svaki čvor ima isti izlazni stepen d, i u kom su grane u d-boja obojene, iz svake dve sa istim početnim čvorom su obojene različito.

Problem bojenja putanja je problem bojenja grana u usmerenom grafu sa čvorovima koji imaju isti broj izlaznog stepena, na takav način da rezultujući automaton ima sinhronizacionu reč. Trahtman 2009 je rešio problem bojenja putanja dokazavši da takav način bojenja se može izvesti kada je graf čvrsto povezan i aperiodičan.

Ramsey's theorem razmatra problem bojenja к-bojama grana velikog kompletnog grafa K_n, da i se izbeglo kreiranje monohromatičnog kompletnog podgrafa K_s , veličine s. Prema teoremi postoji broj R_k(s) takav da, svaki n ≥ R(s) to bojenje nije moguće. Na primer: R₂(3) = 6, ako su grane grafa K₆ dvobojne, uvek će biti monohromatičan trougao.

Putanja u grafu sa obojenim granama, u kom se ni jedna boja ne ponavlja se naziva duga. A graf je obojen u dugu ako postoji duga – putanja između svaka dva čvora.

Primene

Bojenje kompletnih grafova se može koristiti da bi se organizovale Begerov sistem takmičenja u što manje rundi, tako da bi svaki par suparnika igrao sa svakim; u ovoj primeni čvorovi su takmičari u turniru, a grane su partije, a boje su runde u kojima se igra. Slične tehnike se mogu koristiti i za takmičenja koja ne spadaju u Begerov sistem. Na primer, u Nacionalnoj fudbalskoj ligi, parovi timova koji će igrati jedni protiv drugih, u određenoj godini se određuje, na osnovu prošlogodišnjih rezultata, i onda je algoritam za bojenje grafova primenjen na graf koji je formiran od strane uparivanja da bi se svaka utakmica dodelila vikendu u kom će se igrati. Za ovu primenu Vizing teorema implicira, da koji god par uparivanja se odabere (sve dok dva tima ne igraju jedan protiv drugog u istoj sezoni), dokazuje da je uvek moguće naći raspored koji koristi jedan vikend više od broja utakmica za jedan tim.

Open shop scheduling (raspored otvorene proizvodnje) je problem razvrstavanja procesa proizvodnje, u kom imamo set objekata koji treba da se proizvedu, svaki objekat ima set zadataka koji moraju biti obavljeni na svakom tom objektu, i svaki zadatak se mora obaviti na specifičnoj mašini, sprečavajući bilo koji drugi zadatak koji zahteva istu mašinu, da bude obavljen u isto vreme. Ako svi zadaci imaju istu dužinu, onda ovaj problem može biti formalizovan kao jedan od problema bojenja bipartitnog multigrafa, u kom čvorovi na jednoj strani bipartitnog grafa predstavljaju objekte koje treba proizvesti, a čvorovi na drugoj strani predstavljaju mašine koje rade zadatke, a grane su zadaci koje treba odraditi, a boje su vremena u kom svaki zadatak sme da se izvršava. Pošto bipartitno bojenje može da se izvršava u polinomnijalnom vremenu, isto važi i za ovaj slučaj otvorene proizvodnje.

Gandham, Dawande & Prakash 2005 su izučavali problem raspoređivanja veza u deljenju vremena TDMA (time division multiple access) mreži komunikacije senzora za mrežu kao varijantu bojenja grana. U ovom problemu, mora se odabrati vremenski slot za grane bežičnom komunikacionom mrežom tako da svaki čvor nesmetano komunicira sa svakim svojim susednim čvorom. Korišćenjem jakog bojenja grana(i korišćenjem 2 vremenska slota za svaku obojenu granu i po jedan za svaki pravac) bi rešilo problem ali bi se koristilo više vremenskih slotova nego što je neophodno. Umesto toga, oni traže bojenje usmerenog grafa koji je formiran tako što su duplirane sve neusmerene grane mreže, uz to da svaka usmerena grana uvek ima različitu boju od grane koja izlazi iz v i komšija od v. Oni predlažu heuristiku za ovaj problem zasnovanu na distribuirajućem algoritmu za (Δ + 1)-bojenje grana zajedno sa postprocesuirajućom fazom koja ih raspoređuje tako da ne mogu da se mešaju jedna sa drugom.

U optičkoj komunikaciji, problem bojenja putanje dodeljenim bojama parovima čvorova koji žele da komuniciraju jedni sa drugima, i putanje kroz optičke komunikacije za svaki par, uz zabranu da ni jedne dve putanje koje dele isti optički segment, koriste istu frekvenciju. Putanje koje prolaze kroz istu komunikacioni prekidač, ali ne kroz bilo koji segment vlakana, smeju da imaju istu frekvenciju. Kada je uspostavljena komunikacija mreže u obliku zvezde, jednim centralnim prekidačem koji je povezan odvojenim vlaknima od čvorova, problem bojenja putanje se može modelovati isto kao problem bojenja grana u grafu ili multigrafu, u kom komunikacioni čvorovi grafa formiraju temena grafa, parovi čvorova koji žele da komuniciraju sa granama grafa i frekvencije koje se mogu koristiti za svaki par formiraju boje u problem bojenja ivica.

Za komunikacione mreže sa generalnijom topologijom drveta, lokalno bojenje putanja za zvezdane mreže definisano je sa svakim prekidačem u mreži, može se spojiti zajedno sa jednim globalnim rešenjem.

Otvoreni problemi

Jensen & Toft 1995 su naveli 23 otvorena problema koji uključuju bojenje grafova. To su:

• Pretpostavku Goldberg 1973 da hromatski indeks i frakcioni indeks, su jedan sa drugim, što bi dozvolilo da hromatski indeks bude otprilike sa jednom bojom u polinomijalnom vremenu.
• Nekoliko pretpostavki Jakobsen i drugih, vezane za strukturu kritičnih grafova za bojenje ivica, grafova klase 2, čiji podgraf ima ili manji maksimalni stepen čvora nego graf klase 1. Jakobsen je smatrao da svaki kritični graf ima neparan broj temena, ali vremenom ovo je dokazano da nije tačno. Nekoliko dodatnih pretpostavki koje ovo oslabljuju, da ograničenje za broj čvorova kritičnih grafova i kritičnih multigrafova ostaje otvorena.
• Vizing problem klasifikovanja maksimalnog stepena koji je moguć i za klasu 2 planarnog grafa.
• Popunjeni podgraf A. J. W. Hilton stoji da grafovi sa stepenom koji je najmanje n/3 su ili klase 1, ili sadrže podgraf sa istim stepenom Δ , kao originalni graf, i neparnim brojem k temena, tako da je broj grana u podgrafu veći od Δ(k − 1)/2. Slična je i pretpostavka Herbert Grötzsch i Paul Seymour  koja stavlja planarne grafove na mesto grafova sa veoma visokim stepenima.
• Pretpostavka Chetwynd i Hilton (verovatno se vraćajući na delo Gabriel Andrew Dirac) koji razmatraju da regularni graf sa parnim brojem n čvorova, i stepenom najmanjim n/2 pripadaju klasi 1.
• Pretpostavka Claude Berge i D. R. Fulkerson, da 6-regularni graf formiran tako što se duplira svaka grana 3-regularnog prostog grafa, koji nema mostove, može biti obojen sa 6 boja.
• Pretpostavka Fiorini i Wilson da svaki planarni graf koji nema trougao, sem claw K_1,3, nije jedinstveno bojenje.

Trenutna pretpostavka je: ako je G d-regularni planarni multigraf, onda G je d grana-obojivo, a ako i samo ako je G neparno d-grana povezano. Ovo se može rešavati kao generalizacija teoreme o 4 boje kada je d=3. Maria Chudnovsky, Katherine Edwards i Paul Seymour су доказали да 8-регуларни планарни мултиграф има хроматски број 8.

Литература

• Akiyama, Jin; Exoo, Geoffrey; Harary, Frank (1980), „Covering and packing in graphs. III. Cyclic and acyclic invariants”, Mathematica Slovaca, 30 (4): 405—417, MR 595302 .
• Alon, Noga (2003), „A simple algorithm for edge-coloring bipartite multigraphs”, Information Processing Letters, 85 (6): 301—302, MR 1956451, doi:10.1016/S0020-0190(02)00446-5 .
• Alon, Noga; Sudakov, Benny; Zaks, Ayal (2001), „Acyclic edge colorings of graphs”, Journal of Graph Theory, 37 (3): 157—167, MR 1837021, doi:10.1002/jgt.1010 .
• Andersen, Lars Døvling (1977), „On edge-colourings of graphs”, Mathematica Scandinavica, 40 (2): 161—175, MR 0465922 . As cited by Chen, Yu & Zang 2011.
• Appel, K.; Haken, W. (1976), „Every planar map is four colorable”, Bulletin of the American Mathematical Society, 82 (5): 711—712, MR 0424602, doi:10.1090/S0002-9904-1976-14122-5 .
• Bahmani, Bahman; Mehta, Aranyak; Motwani, Rajeev (2010), „A 1.43-competitive online graph edge coloring algorithm in the random order arrival model”, Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '10), стр. 31—39 .
• Bar-Noy, Amotz; Motwani, Rajeev; Naor, Joseph (1992), „The greedy algorithm is optimal for on-line edge coloring”, Information Processing Letters, 44 (5): 251—253, doi:10.1016/0020-0190(92)90209-E .
• Barrett, C.L.; Istrate, G.; Kumar, V.S.A.; Marathe, M.V.; Thite, S.; Thulasidasan, S. (2006), „Strong edge coloring for channel assignment in wireless radio networks”, Proc. Fourth Annual IEEE International Conference on Pervasive Computing and Communications Workshops (PerCom Workshops 2006), стр. 106, ISBN 978-0-7695-2520-4, doi:10.1109/PERCOMW.2006.129 .
• Biggs, Norman (1972), Guy, Richard K., ур., „An edge-colouring problem”, Research Problems, American Mathematical Monthly (9 изд.), 79 (9): 1018—1020, JSTOR 2318076 .
• Biggs, Norman (1979), „Some odd graph theory”, Second International Conference on Combinatorial Mathematics, Annals of the New York Academy of Sciences, 319, стр. 71—81, doi:10.1111/j.1749-6632.1979.tb32775.x .
• Björklund, Andreas; Husfeldt, Thore; Koivisto, Mikko (2009), „Set partitioning via inclusion-exclusion”, SIAM Journal on Computing, 39 (2): 546—563, MR 2529771, doi:10.1137/070683933 .
• Bosák, Juraj (1972), „Chromatic index of finite and infinite graphs”, Czechoslovak Mathematical Journal, 22(97): 272—290, MR 0309777 .
• Bosák, Juraj; Nešetřil, Jaroslav (1976), „Complete and pseudocomplete colourings of a graph”, Matematicky Časopis Slovenskej Akadémie Vied, 26 (3): 171—184, MR 0439672 .
• Cai, X. S.; Perarnau, G.; Reed, B. A.; Watts, A. B. (2014), Acyclic edge colourings of graphs with large girth, arXiv:1411.3047  .
• Burke, E.; De Werra, D.; Kingston, J. (2004), „5.6.5 Sports Timetabling”, Ур.: J. L., Gross; Yellen, J., Handbook of Graph Theory, CRC Press, стр. 462, ISBN 978-1-58488-090-5 .
• Chen, Guantao; Yu, Xingxing; Zang, Wenan (2011), „Approximating the chromatic index of multigraphs”, Journal of Combinatorial Optimization, 21 (2): 219—246, MR 2770056, doi:10.1007/s10878-009-9232-y .
• Chudnovsky, Maria; Edwards, Katherine; Seymour, Paul (2012), Edge-colouring eight-regular planar graphs, arXiv:1209.1176  .
• Cole, Richard; Hopcroft, John (1982), „On edge coloring bipartite graphs”, SIAM Journal on Computing, 11 (3): 540—546, MR 664720, doi:10.1137/0211043 .
• Cole, Richard; Kowalik, Łukasz (2008), „New linear-time algorithms for edge-coloring planar graphs”, Algorithmica, 50 (3): 351—368, MR 2366985, doi:10.1007/s00453-007-9044-3 .
• Cole, Richard; Ost, Kirstin; Schirra, Stefan (2001), „Edge-coloring bipartite multigraphs in O(E log D) time”, Combinatorica, 21 (1), MR 1805711, doi:10.1007/s004930170002 .
• Cranston, Daniel W. (2006), „Strong edge-coloring of graphs with maximum degree 4 using 22 colors”, Discrete Mathematics, 306 (21): 2772—2778, MR 2264374, doi:10.1016/j.disc.2006.03.053 .
• Eppstein, David (2008), „The topology of bendless three-dimensional orthogonal graph drawing”, Ур.: Tollis, Ioannis G.; Patrignani, Marizio, Proc. 16th Int. Symp. Graph Drawing, Lecture Notes in Computer Science, 5417, Heraklion, Crete: Springer-Verlag, стр. 78—89, arXiv:0709.4087  .
• Eppstein, David (2010), „Regular labelings and geometric structures”, Proc. 22nd Canadian Conference on Computational Geometry (CCCG 2010) (PDF), University of Manitoba, arXiv:1007.0221 , Архивирано из оригинала (PDF) 20. 03. 2012. г., Приступљено 25. 05. 2015 .
• Erdős, Paul; Wilson, Robin J. (1977), „Note on the chromatic index of almost all graphs” (PDF), Journal of Combinatorial Theory, Series B, 23 (2–3): 255—257, doi:10.1016/0095-8956(77)90039-9 .
• Erlebach, Thomas; Jansen, Klaus (2001), „The complexity of path coloring and call scheduling”, Theoretical Computer Science, 255 (1–2): 33—50, MR 1819065, doi:10.1016/S0304-3975(99)00152-8 .
• Fiamčik, J. (1978), „The acyclic chromatic class of a graph”, Math. Slovaca, 28: 139—145 .
• Fiorini, S.; Wilson, Robin James (1977), Edge-colourings of graphs, Research Notes in Mathematics, 16, London: Pitman, ISBN 978-0-273-01129-3, MR 0543798 .
• Folkman, Jon; Fulkerson, D. R. (1969), „Edge colorings in bipartite graphs”, Combinatorial Mathematics and its Applications (Proc. Conf., Univ. North Carolina, Chapel Hill, N.C., 1967), Chapel Hill, N.C.: Univ. North Carolina Press, стр. 561—577, MR 0262112 .
• Fouquet, J.-L.; Jolivet, J.-L. (1983), „Strong edge-colorings of graphs and applications to multi-k-gons”, Ars Combinatoria, 16 (A): 141—150, MR 737086 .
• Frieze, Alan M.; Krivelevich, Michael; Sudakov, Benny (2005), „The strong chromatic index of random graphs”, SIAM Journal on Discrete Mathematics, 19 (3): 719—727(electronic), MR 2191290, doi:10.1137/S0895480104445757 .
• Gabow, Harold N. (1976), „Using Euler partitions to edge color bipartite multigraphs”, International Journal of Computer and Information Sciences, 5 (4): 345—355, MR 0422081, doi:10.1007/BF00998632 .
• Gabow, Harold N.; Nishizeki, Takao; Kariv, Oded; Leven, Daniel; Terada, Osamu (1985), Algorithms for edge-coloring graphs, Tech. Report TRECIS-8501, Tohoku University .
• Gabow, Harold N.; Westermann, Herbert H. (1992), „Forests, frames, and games: algorithms for matroid sums and applications”, Algorithmica, 7 (5–6): 465—497, MR 1154585, doi:10.1007/BF01758774 .
• Galvin, F. (1995), „The list chromatic index of a bipartite multigraph”, Journal of Combinatorial Theory, Series B, 63 (1): 153—158, doi:10.1006/jctb.1995.1011 .
• Gandham, S.; Dawande, M.; Prakash, R. (2005), „Link scheduling in sensor networks: distributed edge coloring revisited”, Proc. 24th INFOCOM, 4, стр. 2492—2501, ISBN 978-0-7803-8968-7, doi:10.1109/INFCOM.2005.1498534 .
• Giotis, I.; Kirousis, L.; Psaromiligkos, K. I.; Thilikos, D. M. (2015), „On the algorithmic Lovász Local Lemma and acyclic edge coloring”, Proceedings of the Twelfth Workshop on Analytic Algorithmics and Combinatorics (ANALCO), стр. 16, ISBN 978-1-61197-376-1, doi:10.1137/1.9781611973761.2 .
• Goldberg, M. K. (1973), „Multigraphs with a chromatic index that is nearly maximal”, Diskret. Analiz. (23): 3—7,72, MR 0354429 . As cited by Chen, Yu & Zang 2011.
• Habib, M.; Péroche, B. (1982), „Some problems about linear arboricity”, Discrete Mathematics, 41 (2): 219—220, MR 676882, doi:10.1016/0012-365X(82)90209-6 .
• Holyer, Ian (1981), „The NP-completeness of edge-coloring”, SIAM Journal on Computing, 10 (4): 718—720, doi:10.1137/0210055 .
• Horák, Peter; Niepel, Ľudovít (1982), „A short proof of a linear arboricity theorem for cubic graphs”, Acta Mathematica Universitatis Comenianae, 40/41: 275—277, MR 686983 .
• Jensen, Tommy R.; Toft, Bjarne (1995), Graph Coloring Problems, New York: Wiley-Interscience, ISBN 978-0-471-02865-9 .
• Karloff, Howard J.; Shmoys, David B. (1987), „Efficient parallel algorithms for edge coloring problems”, Journal of Algorithms, 8 (1): 39—52, MR 875324, doi:10.1016/0196-6774(87)90026-5 .
• Kőnig, D. (1916), „Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre”, Mathematische Annalen, 77 (4): 453—465, doi:10.1007/BF01456961, Архивирано из оригинала 19. 1. 2015. г., Приступљено 25. 5. 2015 .
• Kowalik, Łukasz (2009), „Improved edge-coloring with three colors”, Theoretical Computer Science, 410 (38–40): 3733—3742, MR 2553326, doi:10.1016/j.tcs.2009.05.005 .
• Mahdian, Mohammad (2002), „On the computational complexity of strong edge coloring”, Discrete Applied Mathematics, 118 (3): 239—248, MR 1892971, doi:10.1016/S0166-218X(01)00237-2 .
• Meredith, Guy H. J.; Lloyd, E. Keith (1973), „The footballers of Croam”, Journal of Combinatorial Theory, Series B, 15 (2): 161—166, doi:10.1016/0095-8956(73)90016-6 .
• Misra, J.; Gries, David (1992), „A constructive proof of Vizing's Theorem”, Information Processing Letters, 41 (3): 131—133, doi:10.1016/0020-0190(92)90041-S .
• Muthu, Rahul; Narayanan, N.; Subramanian, C. R. (2007), „Improved bounds on acyclic edge colouring”, Discrete Mathematics, 307 (23): 3063—3069, MR 2371078, doi:10.1016/j.disc.2007.03.006 .
• Nash-Williams, C. St. J. A. (1964), „Decomposition of finite graphs into forests”, Journal of the London Mathematical Society, Second Series, 39: 12, MR 0161333 
• Nemhauser, George L.; Park, Sungsoo (1991), „A polyhedral approach to edge coloring”, Operations Research Letters, 10 (6): 315—322, MR 1128970, doi:10.1016/0167-6377(91)90003-8 .
• Richter, David A. (2011), „How to draw a Tait-colorable graph”, Ур.: Brandes, Ulrik; Cornelsen, Sabine, Proc. 18th International Symposium on Graph Drawing (GD 2010), Lecture Notes in Computer Science, 6502, Springer-Verlag, стр. 353—364, ISBN 978-3-642-18468-0, doi:10.1007/978-3-642-18469-7_32 .
• Sanders, Daniel P.; Zhao, Yue (2001), „Planar graphs of maximum degree seven are class I”, Journal of Combinatorial Theory, Series B, 83 (2): 201—212, doi:10.1006/jctb.2001.2047 .
• Seymour, P. D. (1979), „On multicolourings of cubic graphs, and conjectures of Fulkerson and Tutte”, Proceedings of the London Mathematical Society, Third Series, 38 (3): 423—460, MR 532981, doi:10.1112/plms/s3-38.3.423 .
• Schwenk, Allen J. (1989), „Enumeration of Hamiltonian cycles in certain generalized Petersen graphs”, Journal of Combinatorial Theory, Series B, 47 (1): 53—59, MR 1007713, doi:10.1016/0095-8956(89)90064-6 .
• Shannon, Claude E. (1949), „A theorem on coloring the lines of a network”, J. Math. Physics, 28: 148—151, MR 0030203 .
• Skiena, Steven S. (2008), „16.8 Edge Coloring”, The Algorithm Design Manual (2nd изд.), Springer-Verlag, стр. 548—550, ISBN 978-1-84800-069-8, doi:10.1007/978-1-84800-070-4_16 . See also web site for this section of the book in the Stony Brook Algorithm Repository.
• Soifer, Alexander (2008), The Mathematical Coloring Book, Springer-Verlag, ISBN 978-0-387-74640-1 .
• Tait, P. G. (1880), „Remarks on the colourings of maps”, Proc. R. Soc. Edinburgh, 10: 729 .
• Trahtman, Avraham N. (2009), „The road coloring problem”, Israel Journal of Mathematics, 172 (1): 51—60, arXiv:0709.0099 , doi:10.1007/s11856-009-0062-5 .
• Vizing, V. G. (1964), „On an estimate of the chromatic class of a p-graph”, Diskret. Analiz., 3: 25—30, MR 0180505 .
• Vizing, V. G. (1965), „Critical graphs with given chromatic class”, Metody Diskret. Analiz., 5: 9—17 . (In Russian.)
• Williamson, D. P.; Hall, L. A.; Hoogeveen, J. A.; Hurkens, C. A. J.; Lenstra, J. K.; Sevast'janov, S. V.; Shmoys, D. B. (1997), „Short shop schedules”, Operations Research, 45 (2): 288—294, JSTOR 171745, MR 1644998, doi:10.1287/opre.45.2.288 .
• Zhou, Xiao; Nakano, Shin-ichi; Nishizeki, Takao (1996), „Edge-coloring partial k-trees”, Journal of Algorithms, 21 (3): 598—617, MR 1417666, doi:10.1006/jagm.1996.0061 .