250п|мини|Бојење грана са 3 боје Десагруевсовог графа У области теорија графова, бојење грана графа је додељивање боја, гранама графа тако да две суседне гране немају исту боју. На пример, слика са десне стране показује бојење грана графа плавом, зеленом и црвеном бојом. Бојење грана је једно од неколико различитих типова бојења графова. Проблем бојења грана поставља питање да ли је могуће обојити гране датог графа користећи највише -{к}- различитих боја, за задану вредност -{к}-, или са најмање могуће боја. Минималан број потребних боја за гране датог графа назива се хроматски индекс графа. На пример, гране графа са слике могу бити обојене са три боје али не могу бити обојене са две, дакле дати граф има хроматски број три.
По Визинговој теореми, број потребних боја да би се обојиле гране простог графа је или његов максимални степен или . За неке графове, као што су бипартитни графови и високо степени планарни графови, број боја је увек , а за мултиграфове, број боја може бити чак и . Постоје алгоритми полимијалне временске сложености који рачунају оптимално бојење бипартитних графова, и бојење небипартитних простих графова који користе највише боја; ипак, општи проблем проналажења оптималног бојења грана је НП-комплетан и најбржим знаним алгоритмима за то је неопходно експоненцијално време. Проучаване су многе варијације проблема бојења грана, у којима додељивање боја грана мора задовољити и друге услове, а не само услов о суседним гранама. Бојење грана има примену у проблемима распоређивања и у додељивању фреквенције за оптичко влакно мреже.
Примери Циклични граф може имати гране обојене са две боје, ако је дужина циклуса парна: наизменичним мењањем боја у циклусу. Али ако је дужина непарна, потребне су три боје., problem 16.4. стр. 133.
250п|мини| Геометријска конструкција бојења грана комплетног графа са 7 боја. Свака од седам боја има једну грану од центра до чвора полигона и три гране нормалне на њих.
Комплетан граф -{Кn}- са -{n}- чворова може имати гране обојене са бојом, када је -{n}- паран број; ово је посебан случај Бараниаиове теореме. доказује следећу геометријску конструкцију бојења у овом случају: поставити -{n}- показивача на темена и центар регуларног једностраног полигона. За сваку класу боје, треба укључити једну грану од центра до једног од темена полигона, и све нормалне гране које повезују парове темена полигона. Ипак када је -{n}- непаран, потребно је -{n}- боја: свака боја може бити употребљена за грана, a -ти део од укупног броја., problem 16.5. стр. 133. Чињеница да треба или боја је последица Vizing's theorem.
Неколико аутора је проучавало бојење грана непарних графова, -{n}--регуларних графова у којима чворови представљају тимове са играча изабраних из скупа од 2 играча, и у којима гране представљају могућа упарења ових тимова (са једним играчем остављеним као "непаран човек напољу" да суди). Случај у коме је даје добро познат Питерсонов граф. Као што објашњава проблем (за ), играчи желе да нађу распоред за оба упарења тако да сваки тим игра сваку од својих 6 утакмица различитим данима у недељи, са недељом као слободним даном; тј, математички формулишући проблем, они желе да нађу 6 регуларних непарних графова са гранама обојеним са 6 боја. Када је -{n}- једнако 3,4 или 8, бојење грана захтева боју, али када је 5, 6, или 7 потребно је само -{n}- боја.; ;
Дефиниције Као код бојења чворова графа, бојење грана графа, када није другачије наглашено, подразумева да увек буде правилно бојење грана, што значи да се двема суседним гранам не сме доделити иста боја. Сматра се да су две гране суседне када имају заједнички чвор. Бојења грана графа -{G}- може се посматрати као бојење чворова линијског графа , графа који има чвор за сваку грану графа -{G}- и грану за сваки пар суседних грана из графа -{G}-.
Правилно бојење грана са -{k}- различитих боја се зове (правилно) -{k}--бојење грана. За граф који има својство (правилног) -{k}--бојења грана, каже се да може бити -{k}--обојив. Најмањи број боја потребних у (правилном) бојењу грана графа -{G}- је хроматски индекс, или хроматски број грана . Хроматски индекс је такође понекад записан у нотацији ; у овој нотацији индекс (потписани знак) 1 указује да су гране једнодимензиони објекти. Граф је -{k}--хроматски ако је хроматски индекс тачно -{k}-. Хроматски индекс не треба мешати са хроматским бројем или , минималним бројем боја потребних за правилно бојење чворова графа -{G}-.
Уколико се не каже другачије, претпоставља се да су сви графови прости, за разлику од мултиграфа у којима две или више грана могу повезивати исти пар чворова и у којима може бити петља са самим собом (једним чвором). За многе проблеме у бојењу грана, прости графови се понашају другачије од мултиграфова, па је неопходан додатни напор да би се прошириле теореме везане за бојење грана простих графова на случај мултиграфа.
Везе са уклапањем мини|Овај 3-регуларан планарни граф има 16 темена и 24 гране, али само 7 грана је у максималном подударању. Због тога захтева 4 боје приликом бојења грана. Подударање у графу 'G' је скуп грана, тако да никоје две нису обојене истом бојом; савршено подударење је подударање које укључује ивице које дотичу све чворове графа, и максимално подударање је подударање где се укључује што је више могуће грана. У бојењу графа, скуп грана са једном од боја морају да буду несуседне тако да формирају подударање. Бојење грана графа је исто као и подела графа на дисјунктне подграфе.
Ако је број максималних подударања у графу мала, онда ће бити потребно пуно упаривања да би се покриле све гране графа. Формалније речено, ако граф има -{m}- грана, и ако највише грана припадају максималном подударању онда у сваком бојењу графа се мора користити најмање различитих боја. На пример, -{16-vertex}- планаран граф приказан у илистрацији има ивица. У овом графу се не може наћи савршено упаривање; за, ако је на средњем делу извршено подударање, преостале неупарене чворове могу да се групишу у три, различито повезане компоненте са четири или пет чворова и компоненте са непарним бројем чворова не могу имати савршена подударавања. Међутим граф има максимално подударање са седам грана тако да је . Тако је број боја потребних за бојење графа најмање 24/7 и како тај број мора бити цео број, значи најмање четири.
За регуларан граф степана -{k}-} који нема савршено подударење, доња граница може да буде барем потребних боја. Нарочито је ово тачно за регуларан граф са непарним бројем чворова (као што су непарни комплетни графови); за овакве графове, преко лема о руковању, -{k}- мора да буде парно. Међутим, неједнакост не објашњава у потпуности хроматски индекс у сваком регуларном графу, зато што постоје регуларни графови који имају савршено поклапање, али нису k-обојиви. На пример, Питерсонов граф је регуларан, са и грана у савршеном подударању, али нема 3-бојење. Везе са степеном Визингова теорема Гранични хроматски број графа -{G}- је веома тесно везан са максималним степеном , највећим бројем грана инцидентних сваком чвору -{G}-. Очигледно , ако се различитих грана стапају у чвор В и све ове гране морају бити друге боје од осталих које се стапају у тај чвор, а то може бити могуће само ако има најмање боја на располагању. Визингова теорема(по -{Vadim G. Vizing}- који је објавио ово 1964) тврди да је ова веза јако уска за сваки граф гранични хроматски број је или или .
Када је , каже да је у класи 1, иначе је у класи 2.
Сваки бипартитан граф је класе 1, и скоро сви остали графови су класе 1. Међутим проблем је НП-комплетан за одређивање да ли је произвољни граф класе 1.
је доказао да планарани графови максималног степена од најмање осам су класе 1 I истовремено да су такви и планарни графови маскималног степена седам или шест. С друге стране постоје планарни графови маскималног степена од два до пет, који су класе два. Ово је доказано за графове маскималног степена седам. Неповезани планарни кубни графови су сви класе 1; ово је еквивалентна форма 4 боја теореме.; Регуларни графови 1-факторизација "к"-регуларног графа, подграф са гранама графа у савршеном поклапању је исто као и "к"-бојење грана графа. Регуларни граф има факторизацију један и то само ако је класе један. Специјалан случај овога је 3-бојење кубног графа(3-регуларно) и још понекад називан Таит бојење.
Нема сваки регуларни граф факторизацију један, на пример Питерсонов граф нема. У генералном случају 'снаркови' су дефинисани као графови који, као Питерсонов граф, су неповезани 3-регуларни класе два.
Према сваки бипартитни регуларни граф има један факторизацију. Та теорема је изнета раније у смислу "пројективних конфигурација" и доказана је од стране -{Ernst Steinitz}-. Мултиграфови
мини| -{Shannon multigraph}- степена 6, степен гранања 3, потребно 9 боја За мултиграфове код којих различите паралелне гране могу повезати иста два чвора резултат је сличан, али лошији него код -{Vizing's theorem}- у смислу граничног хроматског броја , маскималног степена , и степена гранања и маскималног броја грана у било којој групи паралелних грана. Као прост пример који показује да -{Vizing's theorem}- не генерализује се на мултиграфове узимамо у разматрање -{Shannon multigraph}-, мултиграф са три чвора и три групе по , паралелних грана које повезују сваки од три чвора. У овом примеру , (сваки чвор је инцидентан са само две од три групе од по паралелних грана), али је гранични хроматски број (има три грана укупно, сваке две су суседне тако да све гране морају имати различиту боју у односу на остале). У резултату који је инспирисала -{Vizing}--a, показало се да је ово најгори случај : за сваки мултиграф -{G}-. Додатно за сваки мултиграф -{G}-, , неједначина која се своди на -{Vizing's theorem}- у случају простих графова(за који је ). Алгоритми
Услед тога што је проблем тестирања да ли је граф класе 1 НП-комплетан нема познатог алгоритма у полиномијалном времене зависности за бојење грана било ког графа са оптималним бројем боја.
У сваком случају један број алгоритама је развијен који рекласирају један или више критеријума: они једино раде на подскупу графова или не узимају увек оптималан број боја или се не извршавају увек у времену полиномијалне зависности. Оптимално бојење специјалних класа графова
У случају бипартитнивних графова или мултиграфова максималног степена , оптималан број боја је тачно . су показали да се оптимално бојење графа може урадити у приближно времену линеарне зависности , где је -{м}- број грана графа; простије али спорији алгоритми су описани од стране и . Алгоритам почиње тако што од улазног графа прави регуларни без увећања његовог степена или значајног увећања његове величине, тако што спаја парове чворова који припадају истој страин бипартитивног графа и онда додаје мали број чворова и грана. Затим ако је степен непаран налази једно савршено спајање у времену приближно линеарне зависности, додељује му боју и уклања га из графа, што за последицу има да степен графа постаје паран. Коначно примењује опсервацију да бирањем различитих подскупова грана у Ојлеровом путу граф се раздваја на два регуларна подграфа, да би поделио задатак бојења грана на два мања подзадатка и онда се његов алгоритам извршава рекурзивно на та два. Тотална сложеност је .
За планарне графове са максималним степеном већим од седам оптимални број боја је тачно .
Уз претпоставку да је , могуће је наћи оптимално бојење грана у времену линеарне зависности . Алгоритми који користе више од оптималног броја боја
и описали су алгоритам полиномијалне временске сложености за бојење било ког графа са боја, везујући се за -{Vizing's theorem}-; -{Misra & Gries}- бојења грана графа алгоритам.