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

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

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

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

Примери

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

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

Комплетан граф -{Кn}- са -{n}- чворова може имати гране обојене са Шаблон:Math бојом, када је -{n}- паран број; ово је посебан случај Бараниаиове теореме. Шаблон:Harvnb доказује следећу геометријску конструкцију бојења у овом случају: поставити -{n}- показивача на темена и центар регуларног Шаблон:Math једностраног полигона. За сваку класу боје, треба укључити једну грану од центра до једног од темена полигона, и све нормалне гране које повезују парове темена полигона. Ипак када је -{n}- непаран, потребно је -{n}- боја: свака боја може бити употребљена за Шаблон:Math грана, a Шаблон:Math-ти део од укупног броја.

Неколико аутора је проучавало бојење грана непарних графова, -{n}--регуларних графова у којима чворови представљају тимове са Шаблон:Math играча изабраних из скупа од 2Шаблон:Math играча, и у којима гране представљају могућа упарења ових тимова (са једним играчем остављеним као "непаран човек напољу" да суди). Случај у коме је Шаблон:Math даје добро познат Питерсонов граф. Као што Шаблон:Harvnb објашњава проблем (за Шаблон:Math), играчи желе да нађу распоред за оба упарења тако да сваки тим игра сваку од својих 6 утакмица различитим данима у недељи, са недељом као слободним даном; тј, математички формулишући проблем, они желе да нађу 6 регуларних непарних графова Шаблон:Math са гранама обојеним са 6 боја. Када је -{n}- једнако 3,4 или 8, бојење грана Шаблон:Math захтева Шаблон:Math боју, али када је 5, 6, или 7 потребно је само -{n}- боја.

Дефиниције

Као код бојења чворова графа, бојење грана графа, када није другачије наглашено, подразумева да увек буде правилно бојење грана, што значи да се двема суседним гранам не сме доделити иста боја. Сматра се да су две гране суседне када имају заједнички чвор. Бојења грана графа -{G}- може се посматрати као бојење чворова линијског графа Шаблон:Math, графа који има чвор за сваку грану графа -{G}- и грану за сваки пар суседних грана из графа -{G}-.

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

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

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

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

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

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

За регуларан граф степана -{k}-} који нема савршено подударење, доња граница може да буде барем Шаблон:Math потребних боја. Нарочито је ово тачно за регуларан граф са непарним бројем чворова (као што су непарни комплетни графови); за овакве графове, преко лема о руковању, -{k}- мора да буде парно. Међутим, неједнакост Шаблон:Math не објашњава у потпуности хроматски индекс у сваком регуларном графу, зато што постоје регуларни графови који имају савршено поклапање, али нису k-обојиви. На пример, Питерсонов граф је регуларан, са Шаблон:Math и Шаблон:Math грана у савршеном подударању, али нема 3-бојење.

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

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

Гранични хроматски број графа -{G}- је веома тесно везан са максималним степеном Шаблон:Math, највећим бројем грана инцидентних сваком чвору -{G}-. Очигледно Шаблон:Math, ако се Шаблон:Math различитих грана стапају у чвор В и све ове гране морају бити друге боје од осталих које се стапају у тај чвор, а то може бити могуће само ако има најмање Шаблон:Math боја на располагању. Визингова теорема(по -{Vadim G. Vizing}- који је објавио ово 1964) тврди да је ова веза јако уска за сваки граф гранични хроматски број је или Шаблон:Math или Шаблон:Math.

Када је Шаблон:Math, каже да је у класи 1, иначе је у класи 2.

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

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

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

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

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

Према Шаблон:Harvnb сваки бипартитни регуларни граф има један факторизацију. Та теорема је изнета раније у смислу "пројективних конфигурација" и доказана је од стране -{Ernst Steinitz}-.

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

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

За мултиграфове код којих различите паралелне гране могу повезати иста два чвора резултат је сличан, али лошији него код -{Vizing's theorem}- у смислу граничног хроматског броја Шаблон:Math, маскималног степена Шаблон:Math, и степена гранања Шаблон:Math и маскималног броја грана у било којој групи паралелних грана. Као прост пример који показује да -{Vizing's theorem}- не генерализује се на мултиграфове узимамо у разматрање -{Shannon multigraph}-, мултиграф са три чвора и три групе по Шаблон:Math, паралелних грана које повезују сваки од три чвора. У овом примеру Шаблон:Math, (сваки чвор је инцидентан са само две од три групе од по Шаблон:Math паралелних грана), али је гранични хроматски број Шаблон:Math(има три Шаблон:Math грана укупно, сваке две су суседне тако да све гране морају имати различиту боју у односу на остале). У резултату који је инспирисала -{Vizing}--a, показало се да је ово најгори случај : Шаблон:Math  за сваки мултиграф -{G}-. Додатно за сваки мултиграф -{G}-, Шаблон:Math, неједначина која се своди на -{Vizing's theorem}- у случају простих графова(за који је Шаблон:Math).

Алгоритми

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

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

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

У случају бипартитнивних графова или мултиграфова максималног степена Шаблон:Math, оптималан број боја је тачно Шаблон:Math. Шаблон:Harvnb су показали да се оптимално бојење графа може урадити у приближно времену линеарне зависности Шаблон:Math, где је -{м}- број грана графа; простије али спорији алгоритми су описани од стране Шаблон:Harvnb и Шаблон:Harvnb. Алгоритам Шаблон:Harvnb почиње тако што од улазног графа прави регуларни без увећања његовог степена или значајног увећања његове величине, тако што спаја парове чворова који припадају истој страин бипартитивног графа и онда додаје мали број чворова и грана. Затим ако је степен непаран Шаблон:Harvnb налази једно савршено спајање у времену приближно линеарне зависности, додељује му боју и уклања га из графа, што за последицу има да степен графа постаје паран. Коначно Шаблон:Harvnb примењује Шаблон:Harvnb опсервацију да бирањем различитих подскупова грана у Ојлеровом путу граф се раздваја на два регуларна подграфа, да би поделио задатак бојења грана на два мања подзадатка и онда се његов алгоритам извршава рекурзивно на та два. Тотална сложеност је Шаблон:Math.

За планарне графове са максималним степеном већим од седам оптимални број боја је тачно Шаблон:Math.

Уз претпоставку да је Шаблон:Math, могуће је наћи оптимално бојење грана у времену линеарне зависности Шаблон:Harvnb.

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

Шаблон:Harvnb и Шаблон:Harvnb описали су алгоритам полиномијалне временске сложености за бојење било ког графа са Шаблон:Math  боја, везујући се за -{Vizing's theorem}-; -{Misra & Gries}- бојења грана графа алгоритам.

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

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

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

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

Једноставно је проверити да ли је граф обојен са једном или две боје, тако да је први нетривијалан случај бојења грана графа провера да ли је граф обојен са 3 боје. Како је Шаблон:Harvnb показао, могуће је тестирати да ли је граф обојен са 3 боје у времену Шаблон:Math, користећи само полиномијалан простор. Иако је временско ограничење експоненцијално, ово је значајно брже него сурова (-{brute force}-) претрага кроз све могуће доделе боја гранама. Сваки повезан 3-регуларан граф са -{n}- темена има Шаблон:Math 3-бојења; сва се могу излистати у времену Шаблон:Math (мало спорије него налажење једног бојења); Како је Greg Kuperberg приметио, граф призме над полигоном са -{n/2}- страница има много бојења, што показује да је ова веза уска.

Применом прецизних алгоритама за бојење чворова линијског графа улазног графа, могуће је оптимално обојити ивице било ког графа са -{m}- грана, без обзира на број потребних боја, у времену 2^mm^O(1) и експоненцијалном простору, или у времену Шаблон:Math и полиномијалном простору (Шаблон:Harvnb).

С обзиром да је бојење грана графа НП-комплетно чак и за три боје, није вероватно да ће фиксни параметар бити послушан када се параметризује по броју боја. Међутим, послушан је за друге параметре. На пример, Шаблон:Harvnb показали су да за граф са подстаблом дубине -{w}-, оптимално бојење грана се може израчунати у времену Шаблон:Math, формула суперекспоненцијално зависи од -{w}-, али само линеарно од броја чворова у графу -{n}-.

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

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

Јединствено 3-обојив уопштени Петерсенов граф Шаблон:Math. Једна од три групе боја представљена је светлом бојом и друге две се могу наћи или ротирањем светлих грана за 40° у сваком правцу или поделом тамног Хамилтоновог циклуса у наизменичне ивице.

Граф је јединствено -{k}--ивично-обојив ако постоји само један начин поделе грана у -{k}- група, игноришући -{k}-! могућих пермутација боја. За Шаблон:Math, једини јединствено -{k}--ивично-обојиви графови су путеви, циклуси и звезде, али за Шаблон:Math и други графови могу да буду јединствено 3-ивично-обојиви. Сваки јединствено 3-ивично-обојив граф има тачно три Хамилтонова циклуса (формирани Хамилтонови циклуси нису јединствено 3-ивично-обојиви, као што је Петерсенов граф Шаблон:Math) за Шаблон:Math. Једини познати непланарни јединствено 3-ивично-обојиви граф је генерализовани Петерсенов граф Шаблон:Math, и претпоставља се да други не постоје.

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

Шаблон:Harvnb истраживали су нерастуће низове бројева Шаблон:Math са особином да постоји одговарајуће бојење грана датог графа -{G}- са -{m₁}- грана прве боје, -{m₂}- грана друге боје, и тако даље. Приметили су да ако је сума низа -{P}- изводљива у овом смислу, и ако је лексикографски већи од низа -{Q}- са истом сумом, онда је и -{Q}- изводљива. Јер, ако је {math|P > Q}} у лексикографском поретку, онда се -{P}- може трансформисати у -{Q}- низом корака, од којих сваки умањује неки од бројева Шаблон:Math за један и увећава неки каснији Шаблон:Math (Шаблон:Math) за један. У смислу бојења грана графа, почевши од бојења које представља -{P}-, сваки од ових корака може се извршити заменом боја -{i}- и -{j}- на Кемпеовом ланцу, најдужи пут грана у ком се смењују две боје. На пример, сваки граф има правилно бојење грана, бојење грана са оптималним бројем боја у којој се величина сваке две групе боја разликује за највише један.

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

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

Као што је повезан са највећим степеном и највећим спаривањем графа, хроматски број је уско повезан и са линеарним арбоцитетом Шаблон:Math графа -{G}-, најмањим бројем линеарних шума (раздвојених група путева) у које се ивице графа могу поделити. Спаривање је специјалан случај линеарне шуме, и обрнуто, свака линеарна шума може бити 2-ивично-обојена, дакле за сваки граф -{G}- важи Шаблон:Math. Акијамина претпоставка тврди да $\mathrm{l}\mathrm{a}(G)\le \lceil \frac{\mathrm{\Delta }+1}{2}\rceil$, одакле би следило Шаблон:Math. За графове са највећим степеном 3, Шаблон:Math је увек тачно 2, па се у том случају веза Шаблон:Math поклапа са везом из Визингове теореме.

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

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

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

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

Низовно бојење грана је проблем у ком је дат граф у ком је свакој ивици додељен низ боја, и треба наћи одговарајуће бојење грана, тако да боја сваке гране буде у њеном низу. Низовни хроматски број графа -{G}- је најмањи број -{k}- такав да, без обзира како се бирају низови боја за ивице, све док свака грана има -{k}- боја у свом низу, бојење је сигурно могуће. Низовни хроматски број је увек већи или једнак од хроматског броја. Динитсова претпоставка о завршетку делимичне латинске коцке се може преформулисати као тврђење да је хроматски број низовног бојења грана комплетног бипартитног графа Шаблон:Math једнак његовом хроматском броју грана, -{n}-. Шаблон:Harvnb разложио је претпоставку доказавши, општије, да у сваком бипартитном графу хроматски број и низовни хроматски број имају исту вредност. Претпоставља се и да важи једнакост између хроматског броја и низовног хроматског број, још општије, за произвољне мултиграфове без самопетљи; ова претпоставка и даље није доказана.

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

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

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

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

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

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

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

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

-{Ramsey's theorem}- разматра проблем бојења -{к}--бојама грана великог комплетног графа Шаблон:Math, да и се избегло креирање монохроматичног комплетног подграфа Шаблон:Math , величине -{s}-. Према теореми постоји број Шаблон:Math такав да, сваки Шаблон:Math то бојење није могуће. На пример: Шаблон:Math, ако су гране графа Шаблон:Math двобојне, увек ће бити монохроматичан троугао.

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

Примене

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

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

Шаблон:Harvnb су изучавали проблем распоређивања веза у дељењу времена -{TDMA}- -{(time division multiple access)}- мрежи комуникације сензора за мрежу као варијанту бојења грана. У овом проблему, мора се одабрати временски слот за гране бежичном комуникационом мрежом тако да сваки чвор несметано комуницира са сваким својим суседним чвором. Коришћењем јаког бојења грана(и коришћењем 2 временска слота за сваку обојену грану и по један за сваки правац) би решило проблем али би се користило више временских слотова него што је неопходно. Уместо тога, они траже бојење усмереног графа који је формиран тако што су дуплиране све неусмерене гране мреже, уз то да свака усмерена грана увек има различиту боју од гране која излази из -{v}- и комшија од -{v}-. Они предлажу хеуристику за овај проблем засновану на дистрибуирајућем алгоритму за Шаблон:Math-бојење грана заједно са постпроцесуирајућом фазом која их распоређује тако да не могу да се мешају једна са другом.

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

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

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

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

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

Тренутна претпоставка је: ако је Шаблон:Math Шаблон:Math-регуларни планарни мултиграф, онда Шаблон:Math је Шаблон:Math грана-обојиво, а ако и само ако је Шаблон:Math непарно Шаблон:Math-грана повезано. Ово се може решавати као генерализација теореме о 4 боје када је Шаблон:Math=3. -{Maria Chudnovsky}-, -{Katherine Edwards}- и -{Paul Seymour}- су доказали да 8-регуларни планарни мултиграф има хроматски број 8.Шаблон:Sfnp

Литература

• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation. As cited by Шаблон:Harvnb.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation. As cited by Шаблон:Harvnb.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation. See also web site for this section of the book in the Stony Brook Algorithm Repository.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation. (In Russian.)
• Шаблон:Citation.
• Шаблон:Citation.