У теорији графова, бојење графова је специјалан случај обележавања графова; оно представља додељивање ознака, које се уобичајено називају "боје", елементима графа над којим постоје одређена ограничења. У свом најједноставнијем облику, то представља начин бојења чворова графа, тако да никоја два суседна чвора не буду обојена истом бојом; ово се назива бојење чворова. На сличан начин, бојење грана додељује боју свакој грани тако да никоје две суседне гране нису обојене истом бојом, а бојење области планарног графа представља додељивање боја свакој области (регији) тако да никоје две области које имају заједничку грану нису обојене истом бојом.

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

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

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

Први резултати у области бојења графова су искључиво били повезани са планарним графовима у виду бојења мапа. Док је покушавао да обоји округе на мапи Енглеске, Францис Гутрије (en. Francis Guthrie) је изнео је претпоставку о четири боје, која каже да су четири боје довољне да се цела мапа обоји тако да никоја два суседна округа нису обојена истом бојом. Гутријеов брат је проследио ову претпоставку свом професору математике Августусу де Моргану (en. Augustus de Morgan) на Лондонском универзитету, који је ово споменуо Вилијаму Хамилтону (en. William Hamilton) 1852. године. Артур Кејли (en. Arthur Cayley) је изнео овај проблем на састанку Друштва математичара Лондона 1879. године. Исте године, Алфред Кемп (en. Alfred Kempe) објавио је научни рад који је тврдио да је доказао исправност, и у наредној деценији проблем четири боје је сматран решеним. За своје достигнуће Кемп је проглашен за члана Краљевског друштва, а касније и за председника Друштва математичара Лондона^[1].

1890. године, Хејвуд (en. Heawood) је истакао да Кемпово тврђење није исправно. Међутим, у својој студији, доказао је теорему о пет боја, према којој било која планарна мапа може бити обојена са не више од пет боја, која је била инспирисана Кемповим идејама. У наредном веку, велика количина научног рада и теорија је развијана како би се број боја смањио на четири, све док теорема о четири боје коначно није била доказана 1976. године од стране Кенета Епла(en. Kenneth Appel) и Волфганга Хакена (en. Wolfgang Haken). Доказ се вратио идејама Хејвуда и Кемпа^[2]. Доказ теореме о четири боје је такође вредан пажње јер је први велики компјутерски потпомогнут доказ.

1912. године, Џорџ Дејвид Биркхоф (en. George David Birkhoff) је увео хроматски полином у студију о проблему бојења, који је сведен на Татов полином (en. Tutte) заснован на важним Татовим структурама у алгебарској теорији графова. Кемп је већ скренуо пажњу на генерални, непланарни случај 1879.^[3] године, који је у раном 20. веку резултирао свођењем бојења планарних графова на бојење површина већег реда.

1960. године, Клод Берж (en. Claude Berge) је формулисао још једну претпоставку о бојењу графова, јаку претпоставку о перфектним графовима, који је изворно био мотивисан информационо-теоретском концепту који се зове нула-грешка капацитета графа који је увео Шенон (en. Shannon). Претпоставка је остала нерешена четрдесет година, све док није била утврђена као прослављена јака теорема о префектним графовима Чудновског, Робертсона, Симора и Томаса 2002. године.

Бојење графова је било проучавано као алгоритамски проблем још од почетка 1970-их: хроматски нумерички проблем је један од Карпових 21 НП-комплетних проблема из 1972. године и отприлике у исто то време су развијени разни алгоритми у експоненцијалном времену, засновани на бектрекингу и на Зиковљевом (ру. Зыков) алгоритму брисања контракција из 1949.Једна од главних примена бојења графова, алокација регистара у компајлерима, представљена је 1981. године.

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

Терминологија коришћења боја за обележивање чворова води порекло од проблема бојења области на мапама. Боје попут црвене и плаве се користе само када је број коришћених боја мали и уобчајено је да се бројчане ознаке узимају из скупа природних бројева {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)²(t-2) и то је заиста P(G, 4) = 72. Хроматски полином укључује најмање исту количину датих информација о бојивости графа G као и његов хроматски број. Заиста, χ је најмањи природан број који није једнак корену хроматског полинома. (слика)

${\displaystyle \chi (G)=\min\{k\,\colon \,P(G,k)>0\}.}$

Хроматски полиноми за одређене графове

Троугао K3	${\displaystyle t(t-1)(t-2)}$
Потпун граф Kn	${\displaystyle t(t-1)(t-2)\cdots (t-(n-1))}$
Стабло са n чворова	${\displaystyle t(t-1)^{n-1}}$
Цикл Cn	${\displaystyle (t-1)^{n}+(-1)^{n}(t-1)}$
Петерсонов граф	${\displaystyle t(t-1)(t-2)(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t-352)}$

Бојење грана графа је правилно бојење ивица графа, што значи да никоје две суседне гране нису обојене истом бојом. Бојење грана са k боја се назива k-бојење-грана и то је еквивалентно проблему дељења грана у укупно k скупова. Најмањи број боја потребан за бојење грана графа G се назива хроматски индекс или хроматски број грана, χ'(G). Тејт бојење (en. Tait) је 3-бојење-ивица кубног графа. Теорема о четири боје је еквивалентна претпоставци да сваки планарни кубни граф без моста признаје Тејт бојење.

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

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

Додејљивање појединачне боје сваком појединачном чвору увек као резултат даје исправно бојење па је

${\displaystyle 1\leq \chi (G)\leq n.\,}$

Једини графови који су једно-обојиви су графови без грана. Комплетан граф ${\displaystyle K_{n}}$ са н чворова захтева ${\displaystyle \chi (K_{n})=n}$ боја. У оптималном бојењу мора постојати барем једна од m грана графа између сваког пара исто обојених чворова, па важи

${\displaystyle \chi (G)(\chi (G)-1)\leq 2m.\,}$

Ако G садржи клику вреличине k, онда је потребно барем k боја за бојење те клике, другим речима, хроматски број је увек већи или једнак величини клике.

${\displaystyle \chi (G)\geq \omega (G).\,}$

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

${\displaystyle \chi (G)\leq \Delta (G)+1.\,}$

Комплетни графови имају ${\displaystyle \chi (G)=n}$ и ${\displaystyle \Delta (G)=n-1}$, графови са непарним циклусима имају ${\displaystyle \chi (G)=3}$ и ${\displaystyle \Delta (G)=2}$. Тако да је за овакве графове ово решење најбоље могуће. У свим другим случајевима, граница се може мало побољшати ; Брокова теорема^[4] тврди да је${\displaystyle \chi (G)\leq \Delta (G)}$ за повезан, прост граф G, осим ако је G комплетан граф или има непаран циклус

Графови са великим бројем кликова имају висок хроматски број, али обрнуто не важи. Гречеов граф је пример четири-хроматског графа без троугла, па се овај пример може уопштит на Мицкелскијеву теорему

Мицкелскијева теорема:Постоје графови произвољно високог хроматског броја без троуглова.

Из Брокове теореме следи да граф са високим хроматским бројем мора имати висок максимални степен чвора. Још једно од локалних својстава из ког произилази висок хроматски број је присуство велике клике. Међутим обојивост није у потпуности локални феномен: граф са високим обимом локално изгледају као стабла зато што су сви циклусу дуги, али његов хроматски број не мора бити 2:

Теорема(Ердос): Постоји граф са произвољно високим обимом и хроматским бројем.

Бојење грана графа G може се представити као бојење његовог линијског графа${\displaystyle L(G)}$, и обрнуто. Стога:

${\displaystyle \chi '(G)=\chi (L(G)).\,}$

Постоји уска повезаност између обојивости грана графа и максималног степена ${\displaystyle \Delta (G)}$. Пошто су све гране инцидентне са истим чвором њихове боје морају бити различите. Па важи:

${\displaystyle \chi '(G)\geq \Delta (G).\,}$

Шта више,

Кенингова теорема: ${\displaystyle \chi '(G)=\Delta (G)}$ ако је G бипартитан.

Уопштено, повезаност је већа него она коју нуди Брокова теорема за бојење чворова:

Визингова теорема: Графу са максималним степеном ${\displaystyle \Delta }$ хроматски број грана једнак је ${\displaystyle \Delta }$ или ${\displaystyle \Delta +1}$.

Граф је к-обојив ако и само ако има ацикличну оријентацију у којој најдужи пут има највише дужину k. Ово је Галаи-Хас-Рој-Витавер теорема.

О бесконачним графовима много мање нам је познато.

Ако су сви коначни подграфови бесконачног графа G k-обојиви, онда је и G, под претпоставком аксиоме избора. Ово је де Брујин-Ердос теорема.

Ако граф потпуно n-бојење за свако n ≥n₀, онда је граф бесконачно потпуно обојив.

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

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

Претрага грубом силом за k-бојење захтева ${\displaystyle k^{n}}$ додела боја сваком од n чворова и проверава да ли је резултат коректан. Рачунати хроматски број и хроматски полином, ова процедура се користи за све ${\displaystyle k=1,\ldots ,n-1}$ и не практично је за све осим за графове веома мале врсте.

Коришћењем динамичког програмиранја и постављањем границе максималног броја независних сетова, к-обојивост се може одредити са временском и просторном сложеношћу ${\displaystyle O(2.445^{n})}$^[5]. Коришћењем принципа инклузије-ексклузије и Јејтсовог алгоритма за брзе зета трансформације, к-обојивост може се одредити у ${\displaystyle O(2^{n}n)}$^[6] за било које к. Бржи алгоритми су познати за 3- и 4-обојивост, који имају временску сложеност ${\displaystyle O(1.3289^{n})}$^[7] и ${\displaystyle O(1.7272^{n})}$^[8].

Контракција ${\displaystyle G/uv}$ графа G је граф добијен одрађивањем чворова u и v , уклањањем свих грана између та два чвора и замењивањем са једним чвором w тако да све гране које су биле инцидентне са u и v сада буду инцидентне са w. Ова операција има важну улогу у анализи бојења графа.

Хроматски број задовољава следећу рекурентну релацију:

${\displaystyle \chi (G)={\text{min}}\{\chi (G+uv),\chi (G/uv)\}}$

према Зикову, где су u и v не суседни чворови, ${\displaystyle G+uv}$ је граф са додатом граном ${\displaystyle uv}$. Неколико алгоритама су базирани на овој рекурентној релацији, и дрво које се добија као резултат извршавања се називај још и Зиковљево дрво. Време извршавања се базира на хеуристици одабира чворова u и v.

Хроматски полином задовољава следећу рекурентну релацију:

${\displaystyle P(G-uv,k)=P(G/uv,k)+P(G,k)}$

Где су u и v суседни чворови и ${\displaystyle G-uv}$ је граф без гране ${\displaystyle uv}$. ${\displaystyle P(G-uv,k)}$ представља број могућих исправних бојења графа када чворови могу имати исте или различите боје. Број исправних бојења добијамо као суму два графа. Ако чворови u и v имају различите боје. Онда такође можемо разматрати и граф где су u и v суседне. Ако u и v имају исту боју, онда можемо разматрати граф у ком су u и v контраковане. Тутова радозналост о томе које још особине графа задовољава рекурентна једначина довела га је до открића бивариантне генерализације хроматског полинома, Татовог полинома.

Претходне чињенице довеле су до настанка рекурзивне процедуре алгориритам брисање-контракција, који формира базу за многе алгоритме бојења графа. Временска сложеност задовољава исту рекурентну једначину као и фибоначијев низ, па је у најгорем случају формула за n чворова и m грана^[9]. Анализа се може убрзати до полиномијалног фактора ${\displaystyle ((1+{\sqrt {5}})/2)^{n+m}=O(1.6180^{n+m})}$разапињућих стабала улазног графа.^[10] У пракси, стратегије сепарације и евалуације и одбијање графовских изоморфизама се користе да би се избегли неки од рекурзивних позива, а време извршавања зависи од хеуристике коришћене за одабир чворова.

Похлепни алгоритам разматра чворове у одређеном редоследу ${\displaystyle v_{1}}$,…,${\displaystyle v_{n}}$ где се чвору ${\displaystyle v_{i}}$ додељује најмања могућа боја која није додељена његовим суседима или се уводи нова боја уколико је неопходна. Квалитет бојења зависи од изабраног редоследа. Постоји бојење са оптималним бројем ${\displaystyle \chi (G)}$ боја. У неким случајевима бојење може испасти лошије; пример је Круна(граф) са n чворова који може бити обојен коришћењем 2 боје, али постоји и редослед који доводи бојења са са ${\displaystyle n/2}$ боја.

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

Ако су чворови поређани по степену чвора, резултат похлепног алгоритма користи највише ${\displaystyle {\text{max}}_{i}{\text{ min}}\{d(x_{i})+1,i\}}$ боја, највише за једнубоју више од највећег степена чвора у графу. Ова хеуристика се назива још и Велш-Повел алгоритам. Још једну хеуристику засновао је Брелаз где се редослед одређује динамички током извршавања програма, следећи чвор се бира тако да буде суседан највећем броју различитих боја. Многи други алгоритми заснивају се на статичком или динамичком одређивању редоследа чворова и такви алгоритми се називају још и алгоритми секвенцијалног бојења.

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

У симетричном графу, детерминистички дистрибуирани алгоритми не могу да пронађу исправно бојење чворова. Стандардна претпоставка је да сваки чвор има јединствени идентфикатор – број од 1...n. Претпоставимо да је n боја потребно да се обоји граф Изазов је смањити број са n на нпр. максимални степен графа увећан за 1.

Праволинијски дистрибуирана верзија похлепног алгоритма за ${\displaystyle \Delta +1}$ -бојење захтева Θ(n)комуникационих рунди у најгорем случају – информације потенцијално морају бити слате са једног на други крај мреже.

Најједноставјнији интересантан пример је n-циклус. Ричар Кол и Узи Вишкин су показали дистрибуирани алгоритам који редукује број боја са n на О(logn) у једном синхроном комуникационом кораку. Понављањем исте процедуре могуће је издвојити 3-бојење n-цикла у О(log*n) комуникационих корак(под претпоставком да имамо јединствене идентификаторе).

Функција log*, итеративни логаритам, је екстремно споро растућа функција, „Скоро константна“. Због овога су Кол и Вишкин поставили питање постојања алгоритма који у константном времену израчунава 3-обојивост н-цикла. Линиал је 1992. Године доказа да није могуће: било који детерминистички дистрибуиран алгоритам захтева Ω(log*n) комуникационих корака да редукује n-бојење на 3-бојење n-цикла.

Проблем бојења страница се такође проучавао у дистрибуираном моделу. Панконези и Рици (2001) су достигли (2 Δ -1) бојење у О(Δ + log*n) времену у овом моделу. Дистрибуирано бојење чворова се по Линиалу примењује и на бојење страница.

Децентрализовани алгоритми су они у којима никакво прослеђивање порука није дозвољено(контраст дистрибуираним алгоритмима где се врши слање порука). Постоје и ефикасни децентрализовани алгоритми. Алгоритам се заснива на томе да чвор зна дали је његов сусед означен истом бојом тј, да ли постоји конфликт. Ово је довољно да алгоритмизасновани на вештачкој интелигенцији одреде бојење графа.

Бојење графова је компјутерски тешко. То је НП-комплетан проблем ако се граф треба обојити са к боја, осим када је к=1 и к=2. Конкретно, НП-тежак проблем је израчунавање хроматског броја. 3-бојење остаје НП-комплетан проблем чак и када се решава планаран граф степена 4.

Најбољи познат алгоритам за апроксимацију израчунава бојење величине највише фактор O(n(log n)⁻³(log log n)²) хроматског броја. За све ε> 0, апроксимисање хроматског броја на ${\displaystyle n^{1-\epsilon }}$ је НП-тежак проблем.

Такође је НП-тежак проблем бојења 3-обојивог графа са 4 боје и к-обојивог графа са кналог.. боја за довољно велико к.

За бојење страница, Визингов доказ даје алгоритам који користи највише Δ+1 боја. Међутим избор једног од два кандидата вредности за хроматски број страница је НП-комплетан проблем. У терминима апроксимационих алгоритама, Визингов алгоритам показује да се хроматски број странице може апроксимизовати до на ${\displaystyle 4/3}$ , и доказано је да не постоји алгоритам ${\displaystyle (4/3-\epsilon )}$ за било које ε > 0.

Бојење чворова моделује неколико проблема усмеравања. У најчистијем облику, датом комплету задатака треба да се доделе временски термини, тако да сваки задатак добије по један такав термин. Задаци могу бити распоређени у било ком редоследу, али парови задатака могу бити у сукобу у смислу да не могу бити буду распоређени у истом термину, на пример зато што се ослањају на исти извор. Одговарајући граф садржи чвор ѕа сваки задатак и грану ѕа сваки сукобљен пар задатака. Хроматски број графа је тачно најмањи распон, оптимално време потребно да се заврше сви задаци без сукоба.

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

Компајлер је компјутерски програм који преводи један компјутерски језик у неки други. Да би се побољшало време извођења резултујућег кода, једна од техника оптимизације је регистарска алокација, где се најкоришћеније вредности преведеног програма чувају у регистрима процесора. Идеално, вредности се додељују регистрима да би остали у регистрима и после употребе.

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

Проблем бојења графа налази многе примене, укључујући и уклапање образаца.

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

Важна класа неправилних проблема бојења проучава се у Ремзијевој теорији, где се гранама графа додељују боје, и нема ограничења при бојењу инцидентних грана. Једноставан пример је теорема о пријатељству, која наводи да ће при бојењу грана К6 комплетног графа са шест чворова се појавити једнобојни троугао; често описана говорећи да свака група од шесторо људи садржи три заједничка странца или три заједничка познаника. Ремзијева теорија се бави генерализовањем ове идеје, тражећи уопштене услове за постојање једнобојних подграфова са датом структуром.