мини|десно|Исправно бојење Петерсеновог графа са 3 боје, што је уједно и минимално решење. У теорији графова, бојење графова је специјалан случај обележавања графова; оно представља додељивање ознака, које се уобичајено називају "боје", елементима графа над којим постоје одређена ограничења. У свом најједноставнијем облику, то представља начин бојења чворова графа, тако да никоја два суседна чвора не буду обојена истом бојом; ово се назива бојење чворова. На сличан начин, бојење грана додељује боју свакој грани тако да никоје две суседне гране нису обојене истом бојом, а бојење области планарног графа представља додељивање боја свакој области (регији) тако да никоје две области које имају заједничку грану нису обојене истом бојом. Бојење чворова представља почетни проблем изучавања ове области и сви остали проблеми бојења се могу свести на њега. На пример, бојење грана неког графа представља бојење чворова линеарног графа, а бојење области планарног графа може се представити као бојење чворова њему одговарајућег двоструког графа. Међутим, проблеми бојења који нису задати у облику бојења чворова се најчешће проучавају онако како су задати. Ово је делом због перспективе, а делом због тога што се неки проблеми најбоље решавају у свом изворном облику, као на пример бојење грана. Договор о коришћењу боја води порекло од бојења држава на мапи, где је свака област морала бити обојена. Ово је сведено на бојење области планарних графова. На основу планарне дуалности то је даље сведено на бојење чворова и у оваквој форми може се применити на све графове. У математичкој и компјутерској репрезентацији, уобичајено се користе првих неколико позитивних или ненегативних целих бројева као "боја". За сет боја се може користити било који коначан скуп бројева. Природа проблема зависи искључиво од броја боја, а не од конкретне боје. Бојење графова има широку практичну као и теоријску примену. Осим уобичајених врста проблема, на проблем бојења могу се задати другачија ограничења у виду начина доделе боја или у виду коришћења конкретних боја. Оно ужива велику популарност јавности у виду популарне игре Судоку. Бојење графова је и даље јако активна област истраживања. Историја Први резултати у области бојења графова су искључиво били повезани са планарним графовима у виду бојења мапа. Док је покушавао да обоји округе на мапи Енглеске, Францис Гутрије (en. Francis Guthrie) је изнео је претпоставку о четири боје, која каже да су четири боје довољне да се цела мапа обоји тако да никоја два суседна округа нису обојена истом бојом. Гутријеов брат је проследио ову претпоставку свом професору математике Августусу де Моргану (en. Augustus de Morgan) на Лондонском универзитету, који је ово споменуо Вилијаму Хамилтону (en. William Hamilton) 1852. године. Артур Кејли (en. Arthur Cayley) је изнео овај проблем на састанку Друштва математичара Лондона 1879. године. Исте године, Алфред Кемп (en. Alfred Kempe) објавио је научни рад који је тврдио да је доказао исправност, и у наредној деценији проблем четири боје је сматран решеним. За своје достигнуће Кемп је проглашен за члана Краљевског друштва, а касније и за председника Друштва математичара Лондона, in . 1890. године, Хејвуд (en. Heawood) је истакао да Кемпово тврђење није исправно. Међутим, у својој студији, доказао је теорему о пет боја, према којој било која планарна мапа може бити обојена са не више од пет боја, која је била инспирисана Кемповим идејама. У наредном веку, велика количина научног рада и теорија је развијана како би се број боја смањио на четири, све док теорема о четири боје коначно није била доказана 1976. године од стране Кенета Епла(en. Kenneth Appel) и Волфганга Хакена (en. Wolfgang Haken). Доказ се вратио идејама Хејвуда и Кемпа. Доказ теореме о четири боје је такође вредан пажње јер је први велики компјутерски потпомогнут доказ. 1912. године, Џорџ Дејвид Биркхоф (en. George David Birkhoff) је увео хроматски полином у студију о проблему бојења, који је сведен на Татов полином (en. Tutte) заснован на важним Татовим структурама у алгебарској теорији графова. Кемп је већ скренуо пажњу на генерални, непланарни случај 1879. године, који је у раном 20. веку резултирао свођењем бојења планарних графова на бојење површина већег реда. 1960. године, Клод Берж (en. Claude Berge) је формулисао још једну претпоставку о бојењу графова, јаку претпоставку о перфектним графовима, који је изворно био мотивисан информационо-теоретском концепту који се зове нула-грешка капацитета графа који је увео Шенон (en. Shannon). Претпоставка је остала нерешена четрдесет година, све док није била утврђена као прослављена јака теорема о префектним графовима Чудновског, Робертсона, Симора и Томаса 2002. године. Бојење графова је било проучавано као алгоритамски проблем још од почетка 1970-их: хроматски нумерички проблем је један од Карпових 21 НП-комплетних проблема из 1972. године и отприлике у исто то време су развијени разни алгоритми у експоненцијалном времену, засновани на бектрекингу и на Зиковљевом (ру. Зыков) алгоритму брисања контракција из 1949.Једна од главних примена бојења графова, алокација регистара у компајлерима, представљена је 1981. године.
Дефиниција и терминологија мини|десно|Овај граф може бити 3-обојен на 12 начина. Бојење чворова Када се користи без икаквих квалификација, бојење графа је скоро увек правилно бојење чворова, наиме, обележавање чворова графа на тај начин да никоја два суседна чвора нису обојена истом бојом. Пошто се чвор са петљом никада не може правилно обојити, јасно је да су графови, коришћени у овом контексту, без петљи.
Терминологија коришћења боја за обележивање чворова води порекло од проблема бојења области на мапама. Боје попут црвене и плаве се користе само када је број коришћених боја мали и уобчајено је да се бројчане ознаке узимају из скупа природних бројева {1, 2, 3, ...}. Бојење коришћењем највише k боја, назива се (правилно) k-бојење. Најмањи број боја, потребан да би се обојио граф G се назива хроматским бројем графа G и означава се са χ(G). Понекад се може наћи и ознака γ(G), пошто се χ(G) такође користи за представљање Ојлерове карактеристике графа. Граф који се може обојити са (правилним) k бојењем се назива k-обојив. Граф је k-хроматски ако је његов хроматски број k. Скуп чворова којима је додељена иста боја се назива класа те боје, свака таква класа формира независни скуп. Према томе, k-бојење је исто што и подела чворова графа на независне скупове чворова исте боје, из чега проистиче да термини k-партитан и k-обојив имају исто значење. Хроматски полином Хроматски полином је број различитих начина на који дати граф може бити обојен користећи не више од произвољно задатог броја боја. На пример, коршћењем три боје, граф са слике десно може бити обојен на 12 различитих начина. Уколико би се користиле две боје, граф не би уопште могао бити обојен. Са четири боје, може бити обојен на 24 + 4*12 = 72 начина: коришћењем све 4 боје постоји 4! = 24 исправна бојења, а за сваки избор три од четири боје има 12 исправних 3-бојења. Тако да, за граф из примера таблица правилних бојења изгледа овако: Дозвољене боје 1 2 3 4 …Број бојења 0 0 12 72 … Хроматски полином је функција P(G, t) која израчунава број t-бојења графа G. Kao што му име каже, за дати граф G функција је заиста полиномијална за t. На пример, за граф P(G, t) = t(t-1)2(t-2) и то је заиста P(G, 4) = 72. Хроматски полином укључује најмање исту количину датих информација о бојивости графа G као и његов хроматски број. Заиста, χ је најмањи природан број који није једнак корену хроматског полинома. (слика)
+Хроматски полиноми за одређене графове Троугао K3 Потпун граф Kn Стабло са n чворова Цикл Cn Петерсонов граф
Бојење грана Бојење грана графа је правилно бојење ивица графа, што значи да никоје две суседне гране нису обојене истом бојом. Бојење грана са k боја се назива k-бојење-грана и то је еквивалентно проблему дељења грана у укупно k скупова. Најмањи број боја потребан за бојење грана графа G се назива хроматски индекс или хроматски број грана, χ'(G). Тејт бојење (en. Tait) је 3-бојење-ивица кубног графа. Теорема о четири боје је еквивалентна претпоставци да сваки планарни кубни граф без моста признаје Тејт бојење. Потпуно бојење Потпуно бојење је врста бојења чворова и грана графа. Када се користи без икаквих ограничења, претпоставља се да је потпуно бојење правилно, што значи да суседни чворови и гране нису обојени истом бојом. Потпуни хроматски број χ(G) графа G је најмањи број боја потребан за било које потпуно бојење графа G.
Неозначено/необележено бојење Неозначено/необележено бојење је бојење под утицајем аутоморфизма скупа графова. Ако бисмо интерпретирали бојење графа на чворове као вектор у простору, аутоморфизам би био број пермутација коефицијената бојења. Постоји аналогија са хроматским полиномом који израчунава број бојења графа датим коначним скупом боја.
Особине
Ограничења хроматског броја Додејљивање појединачне боје сваком појединачном чвору увек као резултат даје исправно бојење па је
Једини графови који су једно-обојиви су графови без грана. Комплетан граф са н чворова захтева боја. У оптималном бојењу мора постојати барем једна од m грана графа између сваког пара исто обојених чворова, па важи
Ако G садржи клику вреличине k, онда је потребно барем k боја за бојење те клике, другим речима, хроматски број је увек већи или једнак величини клике.
Двообојиви графови су тачно бипаритни графови, укључујући и стабла и шуме. По теореми о четири боје, сваки планаран граф може бити четири-обојив Похлепно бојење показује да сваки граф може бити обојен са једном више бојом у односу на максималан степен чвора у графу.
Комплетни графови имају и , графови са непарним циклусима имају и . Тако да је за овакве графове ово решење најбоље могуће. У свим другим случајевима, граница се може мало побољшати ; Брокова теорема тврди да је за повезан, прост граф G, осим ако је G комплетан граф или има непаран циклус
Графови са високим хроматским бројем
Графови са великим бројем кликова имају висок хроматски број, али обрнуто не важи. Гречеов граф је пример четири-хроматског графа без троугла, па се овај пример може уопштит на Мицкелскијеву теорему Мицкелскијева теорема:Постоје графови произвољно високог хроматског броја без троуглова.
Из Брокове теореме следи да граф са високим хроматским бројем мора имати висок максимални степен чвора. Још једно од локалних својстава из ког произилази висок хроматски број је присуство велике клике. Међутим обојивост није у потпуности локални феномен: граф са високим обимом локално изгледају као стабла зато што су сви циклусу дуги, али његов хроматски број не мора бити 2: Теорема(Ердос): Постоји граф са произвољно високим обимом и хроматским бројем.
Ограничења хроматског индекса Бојење грана графа G може се представити као бојење његовог линијског графа, и обрнуто. Стога:
Постоји уска повезаност између обојивости грана графа и максималног степена . Пошто су све гране инцидентне са истим чвором њихове боје морају бити различите. Па важи:
Шта више, Кенингова теорема: ако је G бипартитан.
Уопштено, повезаност је већа него она коју нуди Брокова теорема за бојење чворова: Визингова теорема: Графу са максималним степеном хроматски број грана једнак је или .
Друга својства Граф је к-обојив ако и само ако има ацикличну оријентацију у којој најдужи пут има највише дужину k. Ово је Галаи-Хас-Рој-Витавер теорема.
О бесконачним графовима много мање нам је познато. Ако су сви коначни подграфови бесконачног графа G k-обојиви, онда је и G, под претпоставком аксиоме избора. Ово је де Брујин-Ердос теорема. Ако граф потпуно n-бојење за свако n ≥n0, онда је граф бесконачно потпуно обојив.
Алгоритми Полиномијално време