Бојење грана графа

У области теорија графова, бојење грана графа је додељивање боја, гранама графа тако да две суседне гране немају исту боју. На пример, слика са десне стране показује бојење грана графа жутом, зеленом и црвеном бојом. Бојење грана је једно од неколико различитих типова бојења графова. Проблем бојења грана поставља питање да ли је могуће обојити гране датог графа користећи највише к различитих боја, за задану вредност к, или са најмање могуће боја. Минималан број потребних боја за гране датог графа назива се хроматски индекс графа. На пример, гране графа са слике могу бити обојене са три боје али не могу бити обојене са две, дакле дати граф има хроматски број три.

Бојење грана са 3 боје Десагруевсовог графа

По Визинговој теореми, број потребних боја да би се обојиле гране простог графа је или његов максимални степен Δ или Δ+1. За неке графове, као што су бипартитни графови и високо степени планарни графови, број боја је увек Δ, а за мултиграфове, број боја може бити чак и 3Δ/2. Постоје алгоритми полимијалне временске сложености који рачунају оптимално бојење бипартитних графова, и бојење небипартитних простих графова који користе највише Δ+1 боја; ипак, општи проблем проналажења оптималног бојења грана је НП-комплетан и најбржим знаним алгоритмима за то је неопходно експоненцијално време. Проучаване су многе варијације проблема бојења грана, у којима додељивање боја грана мора задовољити и друге услове, а не само услов о суседним гранама. Бојење грана има примену у проблемима распоређивања и у додељивању фреквенције за оптичко влакно мреже.

Примери

Циклични граф може имати гране обојене са две боје, ако је дужина циклуса парна: наизменичним мењањем боја у циклусу. Али ако је дужина непарна, потребне су три боје.

Геометријска конструкција бојења грана комплетног графа K₈ са 7 боја. Свака од седам боја има једну грану од центра до чвора полигона и три гране нормалне на њих.

Комплетан граф Кn са n чворова може имати гране обојене са n − 1 бојом, када је n паран број; ово је посебан случај Бараниаиове теореме. Soifer 2008 доказује следећу геометријску конструкцију бојења у овом случају: поставити n показивача на темена и центар регуларног n − 1 једностраног полигона. За сваку класу боје, треба укључити једну грану од центра до једног од темена полигона, и све нормалне гране које повезују парове темена полигона. Ипак када је n непаран, потребно је n боја: свака боја може бити употребљена за (n − 1)/2 грана, a 1/n-ти део од укупног броја.

Неколико аутора је проучавало бојење грана непарних графова, n-регуларних графова у којима чворови представљају тимове са n − 1 играча изабраних из скупа од 2n − 1 играча, и у којима гране представљају могућа упарења ових тимова (са једним играчем остављеним као "непаран човек напољу" да суди). Случај у коме је n = 3 даје добро познат Питерсонов граф. Као што Biggs 1972 објашњава проблем (за n = 6), играчи желе да нађу распоред за оба упарења тако да сваки тим игра сваку од својих 6 утакмица различитим данима у недељи, са недељом као слободним даном; тј, математички формулишући проблем, они желе да нађу 6 регуларних непарних графова O₆ са гранама обојеним са 6 боја. Када је n једнако 3,4 или 8, бојење грана O_n захтева n + 1 боју, али када је 5, 6, или 7 потребно је само n боја.

Дефиниције

Као код бојења чворова графа, бојење грана графа, када није другачије наглашено, подразумева да увек буде правилно бојење грана, што значи да се двема суседним гранам не сме доделити иста боја. Сматра се да су две гране суседне када имају заједнички чвор. Бојења грана графа G може се посматрати као бојење чворова линијског графа L(G), графа који има чвор за сваку грану графа G и грану за сваки пар суседних грана из графа G.

Правилно бојење грана са k различитих боја се зове (правилно) k-бојење грана. За граф који има својство (правилног) k-бојења грана, каже се да може бити k-обојив. Најмањи број боја потребних у (правилном) бојењу грана графа G је хроматски индекс, или хроматски број грана χ′(G). Хроматски индекс је такође понекад записан у нотацији χ₁(G); у овој нотацији индекс (потписани знак) 1 указује да су гране једнодимензиони објекти. Граф је k-хроматски ако је хроматски индекс тачно k. Хроматски индекс не треба мешати са хроматским бројем χ(G) или χ₀(G), минималним бројем боја потребних за правилно бојење чворова графа G.

Уколико се не каже другачије, претпоставља се да су сви графови прости, за разлику од мултиграфа у којима две или више грана могу повезивати исти пар чворова и у којима може бити петља са самим собом (једним чвором). За многе проблеме у бојењу грана, прости графови се понашају другачије од мултиграфова, па је неопходан додатни напор да би се прошириле теореме везане за бојење грана простих графова на случај мултиграфа.

Везе са уклапањем

Овај 3-регуларан планарни граф има 16 темена и 24 гране, али само 7 грана је у максималном подударању. Због тога захтева 4 боје приликом бојења грана.

Подударање у графу 'G' је скуп грана, тако да никоје две нису обојене истом бојом; савршено подударење је подударање које укључује ивице које дотичу све чворове графа, и максимално подударање је подударање где се укључује што је више могуће грана. У бојењу графа, скуп грана са једном од боја морају да буду несуседне тако да формирају подударање. Бојење грана графа је исто као и подела графа на дисјунктне подграфе.

Ако је број максималних подударања у графу мала, онда ће бити потребно пуно упаривања да би се покриле све гране графа. Формалније речено, ако граф има m грана, и ако највише β грана припадају максималном подударању онда у сваком бојењу графа се мора користити најмање m/β различитих боја. На пример, 16-vertex планаран граф приказан у илистрацији има m = 24 ивица. У овом графу се не може наћи савршено упаривање; за, ако је на средњем делу извршено подударање, преостале неупарене чворове могу да се групишу у три, различито повезане компоненте са четири или пет чворова и компоненте са непарним бројем чворова не могу имати савршена подударавања. Међутим граф има максимално подударање са седам грана тако да је β = 7. Тако је број боја потребних за бојење графа најмање 24/7 и како тај број мора бити цео број, значи најмање четири.

За регуларан граф степана k} који нема савршено подударење, доња граница може да буде барем k + 1 потребних боја. Нарочито је ово тачно за регуларан граф са непарним бројем чворова (као што су непарни комплетни графови); за овакве графове, преко лема о руковању, k мора да буде парно. Међутим, неједнакост χ′ ≥ m/β не објашњава у потпуности хроматски индекс у сваком регуларном графу, зато што постоје регуларни графови који имају савршено поклапање, али нису k-обојиви. На пример, Питерсонов граф је регуларан, са m = 15 и β = 5 грана у савршеном подударању, али нема 3-бојење.

Везе са степеном

Визингова теорема

Гранични хроматски број графа G је веома тесно везан са максималним степеном Δ(G), највећим бројем грана инцидентних сваком чвору G. Очигледно χ′(G) ≥ Δ(G), ако се Δ различитих грана стапају у чвор В и све ове гране морају бити друге боје од осталих које се стапају у тај чвор, а то може бити могуће само ако има најмање Δ боја на располагању. Визингова теорема(по Vadim G. Vizing који је објавио ово 1964) тврди да је ова веза јако уска за сваки граф гранични хроматски број је или Δ(G) или Δ(G) + 1.

Када је χ′(G) = Δ(G), каже да је у класи 1, иначе је у класи 2.

Сваки бипартитан граф је класе 1, и скоро сви остали графови су класе 1. Међутим проблем је НП-комплетан за одређивање да ли је произвољни граф класе 1.

Vizing 1965 је доказао да планарани графови максималног степена од најмање осам су класе 1 I истовремено да су такви и планарни графови маскималног степена седам или шест. С друге стране постоје планарни графови маскималног степена од два до пет, који су класе два. Ово је доказано за графове маскималног степена седам. Неповезани планарни кубни графови су сви класе 1; ово је еквивалентна форма 4 боја теореме.

Регуларни графови

1-факторизација "к"-регуларног графа, подграф са гранама графа у савршеном поклапању је исто као и "к"-бојење грана графа. Регуларни граф има факторизацију један и то само ако је класе један. Специјалан случај овога је 3-бојење кубног графа(3-регуларно) и још понекад називан Таит бојење.

Нема сваки регуларни граф факторизацију један, на пример Питерсонов граф нема. У генералном случају 'снаркови' су дефинисани као графови који, као Питерсонов граф, су неповезани 3-регуларни класе два.

Према Kőnig 1916 сваки бипартитни регуларни граф има један факторизацију. Та теорема је изнета раније у смислу "пројективних конфигурација" и доказана је од стране Ernst Steinitz.

Мултиграфови

Shannon multigraph степена 6, степен гранања 3, потребно 9 боја

За мултиграфове код којих различите паралелне гране могу повезати иста два чвора резултат је сличан, али лошији него код Vizing's theorem у смислу граничног хроматског броја χ′(G), маскималног степена Δ(G), и степена гранања μ(G) и маскималног броја грана у било којој групи паралелних грана. Као прост пример који показује да Vizing's theorem не генерализује се на мултиграфове узимамо у разматрање Shannon multigraph, мултиграф са три чвора и три групе по μ(G), паралелних грана које повезују сваки од три чвора. У овом примеру Δ(G) = 2μ(G), (сваки чвор је инцидентан са само две од три групе од по μ(G) паралелних грана), али је гранични хроматски број 3μ(G)(има три 3μ(G) грана укупно, сваке две су суседне тако да све гране морају имати различиту боју у односу на остале). У резултату који је инспирисала Vizing-a, показало се да је ово најгори случај : χ′(G) ≤ (3/2)Δ(G)  за сваки мултиграф G. Додатно за сваки мултиграф G, χ′(G) ≤ Δ(G) + μ(G), неједначина која се своди на Vizing's theorem у случају простих графова(за који је μ(G) = 1).

Алгоритми

Услед тога што је проблем тестирања да ли је граф класе 1 НП-комплетан нема познатог алгоритма у полиномијалном времене зависности за бојење грана било ког графа са оптималним бројем боја.

У сваком случају један број алгоритама је развијен који рекласирају један или више критеријума: они једино раде на подскупу графова или не узимају увек оптималан број боја или се не извршавају увек у времену полиномијалне зависности.

Оптимално бојење специјалних класа графова

У случају бипартитнивних графова или мултиграфова максималног степена Δ, оптималан број боја је тачно Δ. Cole, Ost & Schirra 2001 су показали да се оптимално бојење графа може урадити у приближно времену линеарне зависности O(m log Δ), где је м број грана графа; простије али спорији алгоритми су описани од стране Cole & Hopcroft 1982 и Alon 2003. Алгоритам Alon 2003 почиње тако што од улазног графа прави регуларни без увећања његовог степена или значајног увећања његове величине, тако што спаја парове чворова који припадају истој страин бипартитивног графа и онда додаје мали број чворова и грана. Затим ако је степен непаран Alon 2003 налази једно савршено спајање у времену приближно линеарне зависности, додељује му боју и уклања га из графа, што за последицу има да степен графа постаје паран. Коначно Alon 2003 примењује Gabow 1976 опсервацију да бирањем различитих подскупова грана у Ојлеровом путу граф се раздваја на два регуларна подграфа, да би поделио задатак бојења грана на два мања подзадатка и онда се његов алгоритам извршава рекурзивно на та два. Тотална сложеност је O(m log m).

За планарне графове са максималним степеном већим од седам оптимални број боја је тачно Δ ≥ 7.

Уз претпоставку да је Δ ≥ 9, могуће је наћи оптимално бојење грана у времену линеарне зависности Cole & Kowalik 2008.

Алгоритми који користе више од оптималног броја боја

Misra & Gries 1992 и Gabow et al. 1985 описали су алгоритам полиномијалне временске сложености за бојење било ког графа са Δ + 1  боја, везујући се за Vizing's theorem; Misra & Gries бојења грана графа алгоритам.

За мултиграфове Karloff & Shmoys 1987 су презентовали алгоритам који се приписује Eli Upfal. Направите улазни мултиграф G Ојлеров додавањем новог чвора који повезује грану сваког чвора непарног степена, наћи Ојлерову путању и изабрати усмерење за путању. Формирати бипартитан граф Hу ком постоје две копије сваког чвора графа G, један са сваке стране бипартације, са граном од чвора u на левој страни бипартитације до чвора v на десној страни бипартитације, кад год постоји усмерена путања од чвора u до v у графу G. Применити на бипартитивном графу алгоритам за бојење грана на H. Свака класа боја у H одговара скупу ивица у G који праве подграф са максималним степеном два; ово је дисјунктна унија путања и циклуса, па тако за сваку класу боја у H могуће је формирати три класе боја у G. Време алгоритма је повезано са бојењем грана бипартитивног графа,  O(m log Δ) користећи алгоритам Cole, Ost & Schirra 2001. Броја боја које овај алгоритам користи је највше $3\left\lceil {\frac {\Delta }{2}}\right\rceil$ близу, али не сасвим једнако са Shannon-овом везом од $\left\lfloor {\frac {3\Delta }{2}}\right\rfloor$ . Такође се може искористити и парелелни алгоритам у истом смеру на исти начин. На истом папиру Karloff и Shmoys такође су представили алгоритам у линеарној временској сложености за бојење мултиграфова са максималним степеном три, са четири боје(користећи везе између Shannon и Vizing) који раде на истом принципу: њихов алгоритам додаје нови чвор да би направили Ојлеров, налазе Ојлерову путању и онда бирају алтернативан скуп грана на тој путањи да би поделили граф у два подграфа максималног степена два. Путање, чак и циклуси од сваког подграфа могу бити обојени са по две боје по подграфу. Након овог корака, свака наредна непарна петља садржи бар једну грану која може бити обојена са једном или две боје које припадају супротном подграфу. Елиминисањем ове гране из непарне петље оставља чворове повезане и та грана може бити обојена користећи две боје за тај подграф.

Похлепни алгоритам за бојење који разматра гране графа или мултиграфа једну по једну, додавањем свакој грани, прву слободну боју може понекад да користи и 2Δ − 1  боја, што може бити приближно двоструко више него што је потребно. Међутим има своје предности које се могу искористити у онлине алгоритмима где улазни граф није познат; у оваквом окружењу његов ‘такмичарска оцена’ је два и то је оптимално: ни један онлине алгоритам не даје боље резултате. Премда ако гране стигну у насумично изабраном редоследу и улазни граф има степен који је у најмању руку логаритамски, онда мања ‘такмичарска оцена’ може бити достигнута.

Неколико аутора је направило претпоставку која говори да је фракционални хроматски индекс било ког мултиграфа(број који се може израчунати у полиномијалној временској сложености користећи линеарно програмирање) је један од хроматских индекса. Ако су ове претпоставке тачне било би могуће да се израчуна број који никада није већи од једног од хроматских индекса у случају мултиграфа, подударајући се са оним познатим из Vizing's theorem за просте графове. Иако је недоказана, генерално ове претпоставке су тачне када је хроматски индекс барем $\Delta +{\sqrt {\Delta /2}}$, што се може десити код мултиграфова.

Прецизни алгоритми

Једноставно је проверити да ли је граф обојен са једном или две боје, тако да је први нетривијалан случај бојења грана графа провера да ли је граф обојен са 3 боје. Како је Kowalik 2009 показао, могуће је тестирати да ли је граф обојен са 3 боје у времену O(1,344ⁿ), користећи само полиномијалан простор. Иако је временско ограничење експоненцијално, ово је значајно брже него сурова (brute force) претрага кроз све могуће доделе боја гранама. Сваки повезан 3-регуларан граф са n темена има О(2^n/2) 3-бојења; сва се могу излистати у времену О(2^n/2) (мало спорије него налажење једног бојења); Како је Greg Kuperberg приметио, граф призме над полигоном са n/2 страница има много бојења, што показује да је ова веза уска.

Применом прецизних алгоритама за бојење чворова линијског графа улазног графа, могуће је оптимално обојити ивице било ког графа са m грана, без обзира на број потребних боја, у времену 2^mm^O(1) и експоненцијалном простору, или у времену О(2,2461^m) и полиномијалном простору (Björklund, Husfeldt & Koivisto 2009).

С обзиром да је бојење грана графа НП-комплетно чак и за три боје, није вероватно да ће фиксни параметар бити послушан када се параметризује по броју боја. Међутим, послушан је за друге параметре. На пример, Zhou, Nakano & Nishizeki 1996 показали су да за граф са подстаблом дубине w, оптимално бојење грана се може израчунати у времену О(nw(6w)^w(w+1)/2), формула суперекспоненцијално зависи од w, али само линеарно од броја чворова у графу n.

Nemhauser & Park 1991 формулисали су проблем бојења грана графа као целобројни програм и описали своје искуство користећи целобројно програмирање за решавање проблема бојења грана графа. Међутим, нису спровели сложенију анализу свог алгоритма.

Додатне Карактеристике

Јединствено 3-обојив уопштени Петерсенов граф G(9,2). Једна од три групе боја представљена је светлом бојом и друге две се могу наћи или ротирањем светлих грана за 40° у сваком правцу или поделом тамног Хамилтоновог циклуса у наизменичне ивице.

Граф је јединствено k-ивично-обојив ако постоји само један начин поделе грана у k група, игноришући k! могућих пермутација боја. За k ≠ 3, једини јединствено k-ивично-обојиви графови су путеви, циклуси и звезде, али за {{{1}}} и други графови могу да буду јединствено 3-ивично-обојиви. Сваки јединствено 3-ивично-обојив граф има тачно три Хамилтонова циклуса (формирани Хамилтонови циклуси нису јединствено 3-ивично-обојиви, као што је Петерсенов граф G(6n + 3, 2)) за n ≥ 2. Једини познати непланарни јединствено 3-ивично-обојиви граф је генерализовани Петерсенов граф G(9, 2), и претпоставља се да други не постоје.

Цртање комплетног бипартитног графа K_3,3 са сваком од своје 3 групе боја нацртаним паралелно.

Folkman & Fulkerson 1969 истраживали су нерастуће низове бројева m₁, m₂, m₃, ... са особином да постоји одговарајуће бојење грана датог графа G са m₁ грана прве боје, m₂ грана друге боје, и тако даље. Приметили су да ако је сума низа P изводљива у овом смислу, и ако је лексикографски већи од низа Q са истом сумом, онда је и Q изводљива. Јер, ако је {math|P > Q}} у лексикографском поретку, онда се P може трансформисати у Q низом корака, од којих сваки умањује неки од бројева m_i за један и увећава неки каснији m_j (i < j) за један. У смислу бојења грана графа, почевши од бојења које представља P, сваки од ових корака може се извршити заменом боја i и j на Кемпеовом ланцу, најдужи пут грана у ком се смењују две боје. На пример, сваки граф има правилно бојење грана, бојење грана са оптималним бројем боја у којој се величина сваке две групе боја разликује за највише један.

De Bruijn–Erdős-ова теорема се може искористити за пребацивање многих својстава бојења грана коначних графова на бесконачне графове. На пример, и Шенонгова и Визингова теорема повезују степен графа са његовим хроматским бројем, обе генерализујући директно на бесконачне графове.

Richter 2011 разматра проблем налажења слике графа задатог кубног графа са својствима да све ивице на цртежу имају једну од три различите косине и да две ивице не леже на истој линији. Ако такво графичко представљање постоји, онда очито те косине грана могу да се искористе као боје у 3-ивичном-бојењу графа. На пример, цртање графа K_3,3 као ивице и дуже дијагонале правилног шестоугла представља 3-ивично-бојење графа на овај начин. Како је Рихтер показао, 3-правилни прости бипартитни граф са датим бојењем, има графички приказ овог типа који представља дато бојење ако и само ако је граф 3-ивично-повезан. За небипартитни граф, услов је мало компликованији: дато бојење се може представити графички ако је двоструки бипартитни покривач графа 3-ивично-повезан, и ако брисањем моногроматског пара грана води до подграфа који и даље није бипартитан. Сви ови услови се могу проверити у полиномијалном времену; међутим, проблем проверавања да ли 4-ивично-обојив 4-правилни граф има графички приказ са гранама са 3 косине, који представља боје као косине, је еквивалентан са проблемом ETR, који је НП-комплетан.

Као што је повезан са највећим степеном и највећим спаривањем графа, хроматски број је уско повезан и са линеарним арбоцитетом la(G) графа G, најмањим бројем линеарних шума (раздвојених група путева) у које се ивице графа могу поделити. Спаривање је специјалан случај линеарне шуме, и обрнуто, свака линеарна шума може бити 2-ивично-обојена, дакле за сваки граф G важи la(G) ≤ χ′(G) ≤ 2 la(G). Акијамина претпоставка тврди да $\mathop {\mathrm {la} } (G)\leq \left\lceil {\frac {\Delta +1}{2}}\right\rceil$, одакле би следило 2 la(G) − 2 ≤ χ′(G) ≤ 2 la(G). За графове са највећим степеном 3, la(G) је увек тачно 2, па се у том случају веза χ′(G) ≤ 2 la(G) поклапа са везом из Визингове теореме.

Други типови бојења

Подела комплетног бипартитног графа K_4,4 у три шуме, показујући да има арборицитет три.

Туов број графа је број боја потребних у бојењу грана графа да задовољи услов да, у сваком путу парне дужине, прва друга половина пута формирају различите низове боја.

Арборицитет графа је најмањи број боја неопходних како ивице сваке боје не би формирале циклус (слично, у обичном бојењу грана, суседне гране не смеју бити исте боје). Тачније, то је најмањи број шума у које ивице графа могу да буду подељене. За разлику од хроматског броја, арборицитет графа се може израчунати у полиномијалном времену.

Низовно бојење грана је проблем у ком је дат граф у ком је свакој ивици додељен низ боја, и треба наћи одговарајуће бојење грана, тако да боја сваке гране буде у њеном низу. Низовни хроматски број графа G је најмањи број k такав да, без обзира како се бирају низови боја за ивице, све док свака грана има k боја у свом низу, бојење је сигурно могуће. Низовни хроматски број је увек већи или једнак од хроматског броја. Динитсова претпоставка о завршетку делимичне латинске коцке се може преформулисати као тврђење да је хроматски број низовног бојења грана комплетног бипартитног графа K_n,n једнак његовом хроматском броју грана, n. Galvin 1995 разложио је претпоставку доказавши, општије, да у сваком бипартитном графу хроматски број и низовни хроматски број имају исту вредност. Претпоставља се и да важи једнакост између хроматског броја и низовног хроматског број, још општије, за произвољне мултиграфове без самопетљи; ова претпоставка и даље није доказана.

Многе друге често проучаване варијације бојења чворова су такође пренесене на бојење грана. На пример, потпуно бојење грана је варијанта некомплетног бојења, регуларно бојење у ком сваки пар боја мора бити представљен са бар једним паром суседних ивица и у ком је циљ да се постигне највећи број искоришћених боја. Јако бојење грана је варијанта јаког бојења, бојење грана у ком сваке 2 гране са суседним чворовима морају имати различиту боју. Јако бојење грана има примену у шемама за доделу канала за бежичне мреже.

Ациклично бојење грана је варијанта ацикличног бојења, бојење грана у ком сваке две групе боја формирају ациклични подграф (односно шуму). Ациклични громатски број графа $G$, означен као $a'(G)$, је најмањи број боја потребних да би се добило правилно ациклично бојење грана графа $G$. Претпоставља се да важи $a'(G)\leq \Delta +2$, где је $\Delta$ највећи степен графа $G$. Тренутно је најбоља веза $a'(G)\leq \lceil 3.74(\Delta -1)\rceil$. Проблем постаје једноставнији када граф $G$ има већи обим. Прецизније, постоји константа $c$ таква да ако је обим графа $G$ бар $c\Delta \log \Delta$, онда важи $a'(G)\leq \Delta +2$. Слично важи и за све $\epsilon >0$, постоји $g$ такво да ако $G$ има обим бар $g$, онда важи $a'(G)\leq (1+\epsilon )\Delta$.

Eppstein 2008 је проучавао 3-ивична-бојења кубних графова са додатним својством да два бихроматска циклуса не деле више од једне заједничке ивице. Показао је да је постојање таквог бојења еквивалентно са постојањем графичког приказа графа на тродимензионалном целобројном координатном систему са ивицама паралелним са координатним осама и свака паралелна линија садржи највише 2 чвора. Ипак, као и обични проблем 3-ивичнног-бојења, налажење бојења овог типа је НП-комплетно.

Тотално бојење је бојење које комбинује бојење чворова и бојење грана, које захтева да и темена и гране буду обојене. Било који случајан пар гране и темена или гране и гране, мора имати различите боје, као и суседна темена. Спекулисано је (комбинацијом Vizing и Brooks' theorem) да било који граф има тотално бојење у ком је максималан број боја максималан степен плус два, али још увек није доказано.

Ако би 3-регуларни граф на површини је 3-гране-обојен, његов дуални граф, формира триагулацију на површини, ком је такође обојена ивица (али ипак није правилно обојена), на такав начин да сваки троугао има једну грану од сваке боје. Друга бојења и оријентације триангулације, са другим локалним ограничењима, како су боје распоређене, на теменима или лицима триангулације, може се користити да би се излистало неколико типова геометријских објеката. На пример, правоугона подела (делови правоугаоне поделе, на мање правоугаонике где се свака три правоугоника спајају у једном темену), може се описати комбинаторно уз “регуларно обележавање”, двобојно бојење ивица триангулационог дела поделе, уз граничење да гране одговарају сваком темену које формира 4 суседне поделе, у којој су боје исте.

Овакво обележавање је паралелно бојењу четвороугаоних подела, у којима се вертикалне гране боје једном, а хоризонталне другом бојом. Слична локална ограничења се односе на распоред у ком обојене грне које се појављују око чвора могу да се користе да стварају праволинијску мрежу уграђујући планарне графове и тродимензионе полиедре са паралелним странама. За сваки од ова три типа регуларних бојења, сет регуларних бојења фиксираних графова формира distributive lattice који може да се искористи да се брзо излистају све геометријске структуре засноване на самом графу (као полиедар са паралелним странама који има исти скелет), или да се нађу структуре које задовољавају додатне услове.

Детерминистички коначни аутомат може бити приказан као усмерени граф у ком сваки чвор има исти излазни степен d, и у ком су гране у d-боја обојене, из сваке две са истим почетним чвором су обојене различито.

Проблем бојења путања је проблем бојења грана у усмереном графу са чворовима који имају исти број излазног степена, на такав начин да резултујући аутоматон има синхронизациону реч. Trahtman 2009 је решио проблем бојења путања доказавши да такав начин бојења се може извести када је граф чврсто повезан и апериодичан.

Ramsey's theorem разматра проблем бојења к-бојама грана великог комплетног графа K_n, да и се избегло креирање монохроматичног комплетног подграфа K_s , величине s. Према теореми постоји број R_k(s) такав да, сваки n ≥ R(s) то бојење није могуће. На пример: R₂(3) = 6, ако су гране графа K₆ двобојне, увек ће бити монохроматичан троугао.

Путања у графу са обојеним гранама, у ком се ни једна боја не понавља се назива дуга. А граф је обојен у дугу ако постоји дуга – путања између свака два чвора.

Примене

Бојење комплетних графова се може користити да би се организовале Бегеров систем такмичења у што мање рунди, тако да би сваки пар супарника играо са сваким; у овој примени чворови су такмичари у турниру, а гране су партије, а боје су рунде у којима се игра. Сличне технике се могу користити и за такмичења која не спадају у Бегеров систем. На пример, у Националној фудбалској лиги, парови тимова који ће играти једни против других, у одређеној години се одређује, на основу прошлогодишњих резултата, и онда је алгоритам за бојење графова примењен на граф који је формиран од стране упаривања да би се свака утакмица доделила викенду у ком ће се играти. За ову примену Vizing теорема имплицира, да који год пар упаривања се одабере (све док два тима не играју један против другог у истој сезони), доказује да је увек могуће наћи распоред који користи један викенд више од броја утакмица за један тим.

Open shop scheduling (распоред отворене производње) је проблем разврставања процеса производње, у ком имамо сет објеката који треба да се произведу, сваки објекат има сет задатака који морају бити обављени на сваком том објекту, и сваки задатак се мора обавити на специфичној машини, спречавајући било који други задатак који захтева исту машину, да буде обављен у исто време. Ако сви задаци имају исту дужину, онда овај проблем може бити формализован као један од проблема бојења бипартитног мултиграфа, у ком чворови на једној страни бипартитног графа представљају објекте које треба произвести, а чворови на другој страни представљају машине које раде задатке, а гране су задаци које треба одрадити, а боје су времена у ком сваки задатак сме да се извршава. Пошто бипартитно бојење може да се извршава у полиномнијалном времену, исто важи и за овај случај отворене производње.

Gandham, Dawande & Prakash 2005 су изучавали проблем распоређивања веза у дељењу времена TDMA (time division multiple access) мрежи комуникације сензора за мрежу као варијанту бојења грана. У овом проблему, мора се одабрати временски слот за гране бежичном комуникационом мрежом тако да сваки чвор несметано комуницира са сваким својим суседним чвором. Коришћењем јаког бојења грана(и коришћењем 2 временска слота за сваку обојену грану и по један за сваки правац) би решило проблем али би се користило више временских слотова него што је неопходно. Уместо тога, они траже бојење усмереног графа који је формиран тако што су дуплиране све неусмерене гране мреже, уз то да свака усмерена грана увек има различиту боју од гране која излази из v и комшија од v. Они предлажу хеуристику за овај проблем засновану на дистрибуирајућем алгоритму за (Δ + 1)-бојење грана заједно са постпроцесуирајућом фазом која их распоређује тако да не могу да се мешају једна са другом.

U оптичкој комуникацији, проблем бојења путање додељеним бојама паровима чворова који желе да комуницирају једни са другима, и путање кроз оптичке комуникације за сваки пар, уз забрану да ни једне две путање које деле исти оптички сегмент, користе исту фреквенцију. Путање које пролазе кроз исту комуникациони прекидач, али не кроз било који сегмент влакана, смеју да имају исту фреквенцију. Када је успостављена комуникација мреже у облику звезде, једним централним прекидачем који је повезан одвојеним влакнима од чворова, проблем бојења путање се може моделовати исто као проблем бојења грана у графу или мултиграфу, у ком комуникациони чворови графа формирају темена графа, парови чворова који желе да комуницирају са гранама графа и фреквенције које се могу користити за сваки пар формирају боје у проблем бојења ивица.

За комуникационе мреже са генералнијом топологијом дрвета, локално бојење путања за звездане мреже дефинисано је са сваким прекидачем у мрежи, може се спојити заједно са једним глобалним решењем.

Отворени проблеми

Jensen & Toft 1995 су навели 23 отворена проблема који укључују бојење графова. То су:

• Претпоставку Goldberg 1973 да хроматски индекс и фракциони индекс, су један са другим, што би дозволило да хроматски индекс буде отприлике са једном бојом у полиномијалном времену.
• Неколико претпоставки Jakobsen и других, везане за структуру критичних графова за бојење ивица, графова класе 2, чији подграф има или мањи максимални степен чвора него граф класе 1. Jakobsen је сматрао да сваки критични граф има непаран број темена, али временом ово је доказано да није тачно. Неколико додатних претпоставки које ово ослабљују, да ограничење за број чворова критичних графова и критичних мултиграфова остаје отворена.
• Vizing проблем класификовања максималног степена који је могућ и за класу 2 планарног графа.
• Попуњени подграф A. J. W. Hilton стоји да графови са степеном који је најмање n/3 су или класе 1, или садрже подграф са истим степеном Δ , као оригинални граф, и непарним бројем k темена, тако да је број грана у подграфу већи од Δ(k − 1)/2. Слична је и претпоставка Herbert Grötzsch и Paul Seymour  која ставља планарне графове на место графова са веома високим степенима.
• Претпоставка Chetwynd и Hilton (вероватно се враћајући на дело Gabriel Andrew Dirac) који разматрају да регуларни граф са парним бројем n чворова, и степеном најмањим n/2 припадају класи 1.
• Претпоставка Claude Berge и D. R. Fulkerson, да 6-регуларни граф формиран тако што се дуплира свака грана 3-регуларног простог графа, који нема мостове, може бити обојен са 6 боја.
• Претпоставка Fiorini и Wilson да сваки планарни граф који нема троугао, сем claw K_1,3, није јединствено бојење.

Тренутна претпоставка је: ако је G d-регуларни планарни мултиграф, онда G је d грана-обојиво, а ако и само ако је G непарно d-грана повезано. Ово се може решавати као генерализација теореме о 4 боје када је d=3. Maria Chudnovsky, Katherine Edwards и 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 .