Gráfok színezése forrásának megtekintése

[[File:Petersen graph 3-coloring.svg|thumb|right|A [[Petersen-gráf]] jó csúcsszínezése 3 színnel, ami a legkevesebb lehetséges szín (kromatikus szám=3).]]
A [[matematika]], azon belül a [[gráfelmélet]] területén a '''[[gráf]]ok színezése''' a [[gráfcímkézés]] speciális esete: bizonyos megszorítások mentén „színeket” (vagy számokat) rendelünk hozzá egy gráf valamilyen alkotóelemeihez. A leggyakoribb formájában a gráf csúcsaihoz történik a hozzárendelés, ez '''csúcsszínezés''' vagy egyszerűen színezés. Ha a gráf éleihez rendelünk színeket, az a gráf '''[[élszínezés]]e''', ha pedig a csúcsok és az élek is színezésre kerülnek, '''[[totális színezés]]ről''' beszélhetünk. [[Síkbarajzolható gráf]] '''tartományszínezésénél''' pedig a lerajzolás tartományaihoz rendelünk színeket.

A gráfszínezéseknél '''jó színezésnek''' azt tekintjük, ha a szomszédos elemek (csúcsszínezésnél az egymással összekötött csúcsok, élszínezésnél az egy csúcsból kiinduló élek, tartományszínezésnél a közös határral rendelkező területek) különböző színűek. Színezés alatt külön jelző nélkül is általában jó színezés értendő.

A gráfok színezése területének kiindulópontjában a csúcsszínezés áll, és a többi színezési probléma is visszavezethető csúcsszínezésre: például egy gráf élszínezése megegyezik [[élgráf]]jának, totális színezése [[Totális színezés|totális gráf]]jának, síkgráf tartományszínezése pedig [[duális gráf|duálisának]] csúcsszínezésével. Mégis, a nem-csúcsszínezési problémákat gyakran eredeti változatukban vizsgálják – ennek oka a perspektíva, egyes problémák, mint az élszínezés, egyszerűen jobban átláthatók, jobban kezelhetők eredeti formájukban.

A színek hozzárendelésének hagyománya a [[térkép]]ek országainak színezéséből ered, ahol a tartományokat szó szerint kiszínezték. Ezt általánosították a síkba [[gráf beágyazása|ágyazott]] gráf tartományainak színezésére. A dualitás miatt ebből csúcsok színezése lett, amit aztán minden gráfra általánosítottak. A matematikai és számítógépes megvalósításokban jellemzően az első néhány pozitív vagy nemnegatív számot használják „színekként”. Bármilyen véges halmaz alkalmas lehet „színhalmaznak” – a színezési probléma természete csak a színek számosságán múlik, nem a minőségükön.

A gráfszínezés területén számos gyakorlati alkalmazással, még több elméleti kihívással lehet találkozni. A klasszikusnak mondható problémák mellett különböző korlátok állíthatók fel a szóba jövő gráfra, a szín hozzárendelésének módjára vagy a színre magára. Jelenleg is igen aktívan kutatott terület.

== Rövid történeti áttekintés ==
{{bővebben|Négyszín-tétel}}

Az első gráfszínezési eredmények [[síkbarajzolható gráf]]okkal voltak kapcsolatosak, a legfontosabb feladat térképek színezése volt. Amíg [[Anglia]] megyéit próbálták meg színekkel ellátni, [[Francis Guthrie]] megfogalmazta a négyszín-sejtést, miszerint 4 szín elegendő a különböző tartományok megfestéséhez, ha szomszédos tartományok különböző színeket kapnak. Guthrie testvére továbbította ezt a kérdést a matematikatanára, [[Augustus De Morgan]] felé, aki szintén megosztotta a sejtést [[William Rowan Hamilton]]nal. [[Arthur Cayley]] 1879-ben vetette fel a problémát a [[London Mathematical Society]] egy találkozóján. Még ebben az évben [[Alfred Kempe]] nyilvánosságra hozta bizonyítását, és egy évtizeden át helyesnek ítélték. Ennek köszönhetően elismerésben is részesült, a Royal Society tagjává választották, és később ő vált a [[London Mathematical Society]] elnökévé is.

1890-ben Heawood belátta, hogy Kempe bizonyítása hibás volt. Bár jó megoldást ő nem talált a problémára, az [[ötszín-tétel]]t sikerült belátnia, vagyis bármilyen síktérkép kiszínezhető 5-nél nem több színnel. Ehhez Kempe ötleteit használta fel. A következő évszázadban rengeteg ötlet merült fel, hogy sikerüljön ezt a számot 4-re leszorítani, végül csak 1976-ban sikerül Kenneth Appelnek és Wolfgang Hakennek helyes bizonyítást adnia. Meglepetésre Heawoord és Kempe elgondolásait használták fel, számottevő kiterjesztés nélkül. A [[négyszín-tétel]] bizonyítása volt az első [[számítógép]]re alapozott bizonyítás.

1912-ben George David Birkhoff vezette be a '''kromatikus polinom'''ot a színezési problémák megsegítésére, amit Tutte általánosított Tutte-polinom néven. Kempe már 1879-ben felhívta a figyelmet a nem síkbeli esetre, és a 20. század elején több eredmény is napvilágot látott magasabb [[dimenzió]]jú felületek kiszínezésének terén.

1960-ban Claude Berge megfogalmazott egy másik gráfszínezéssel kapcsolatos sejtést, az erős [[perfekt gráf]] tételt, ami Shannon információ-elméleti munkásságából eredeztethető. A sejtés 40 évig megoldatlan maradt, 2002-ben sikerült a Chudnovsky, Robertson, Seymour, Thomas által alkotott csoportnak belátnia.

A gráfszínezést az 1970-es évek óta tanulmányozták algoritmuselméleti problémaként. A '''kromatikus szám''' problémája egyike Karp 21 NP-teljes problémájának 1972-ből, nagyjából ebben az időben jelent meg több exponenciális-idejű algoritmus is, mely a '''Zykov-kontrakció'''n alapszik. Az egyik legjelentősebb alkalmazási terület, a [[fordítóprogram]]ok regiszter-allokációja 1981-ben került bevezetésre.

==Definíció és terminológia==<!--a [[Kromatikus szám]] ide irányít-->
[[Fájl:Graph with all three-colourings 2.svg|thumb|right|Ez a gráf 12-féleképpen színezhető ki 3 színnel.]]

===Csúcsszínezés===
Ha egyéb jelző nélkül egy gráf '''színezését''' említjük, csaknem mindig a gráf '''jó csúcsszínezése''' értendő alatta, tehát a gráf csúcsainak színekkel való olyan címkézése, melyben ugyanazon éllel érintkező két csúcs színe mindig különböző. Ha egy csúcsból hurokél indulna ki, a gráfnak nem létezhetne jó csúcsszínezése, ezért ebben a szakaszban csak hurokmentes gráfokat veszünk figyelembe.

A csúcsok címkézésénél a ''színek'' használata a térképek színezésére vezethető vissza. Ha csak 2-3 szín fordul elő, ''piros'', ''kék'' stb. címkéket használnak, de általában úgy tekintik, hogy a címkék az {1, 2, 3, ...} egész számok közül kerülnek ki.

{{anchor|Kromatikus szám}}
Az olyan színezést, ami legfeljebb ''k'' színt használ, (jó) '''''k''-színezésnek''' neveznek.
Az a legkisebb ''k'' szám, amire a ''G'' gráfnak van jó ''k''-színezése, a gráf '''kromatikus száma''' (színezési száma), amit általában χ(''G'')-vel jelölnek. Néha az γ(''G'') jelölést is használatos, mivel a χ(''G'') a gráf [[Euler-karakterisztika|karakterisztikáját]] is jelöli.
Az olyan gráf, amihez tartozik (jó) ''k''-színezés, '''''k''-színezhető''', továbbá '''''k''-kromatikus''', amennyiben kromatikus száma pontosan ''k''.

A színezésnél azonos színt kapott csúcsok halmazát '''színosztálynak''' neveznek. Minden színosztály [[független csúcshalmaz]]t alkot, tehát egy gráf ''k''-színezése ugyanazt jelenti, mint csúcsainak ''k'' független csúcshalmazba való osztása, ezért a ''k''-színezhető és a ''k''-részes gráf fogalmak ugyanazt jelentik.

===Kromatikus polinom===
[[File:Chromatic polynomial of all 3-vertex graphs.png|thumb|200px|A 3 csúcsú nem izomorf gráfok és a hozzájuk tartozó kromatikus polinomok. Az ''E''<sub>3</sub> üres gráf (piros) 1-színezhető, a többi nem. A zöld gráfnak 12 3-színezése létezik.]]
{{fő|Kromatikus polinom}}
Egy gráf '''kromatikus polinomja''' megszámolja a gráf adott számú színnel történő csúcsszínezéseinek lehetőségét. Például a jobb oldalon látható gráfot három színnel tizenkétféleképpen lehet kiszínezni, két színnel egyáltalán nem lehetséges a színezés, négy színnel pedig 24&nbsp;+&nbsp;4⋅12&nbsp;=&nbsp;72-féleképpen lehetséges a színezés: mind a négy színt felhasználva 4!&nbsp;=&nbsp;24 érvényes színezés lehetséges (bármely 4 csúcsú gráfban egy mind a 4 színt felhasználó színezés ''jó'' színezés); a négy színből hármat választva pedig 12 érvényes 3 színezés található. Így tehát a példagráf lehetséges színezések számának táblázata így kezdődik:

{| class="wikitable"
|-
|Felhasználható színek száma || 1 || 2 || 3 || 4 || …
|-
|Színezések száma || 0 || 0 || 12 || 72 || …
|}

A kromatikus polinom olyan ''P''(''G'',&nbsp;''t'') függvény, ami ''G'' ''t''-színezéseit számolja meg. Ahogy a neve is mutatja, adott ''G'' esetén a függvény valóban ''t'' [[polinom]]ja. A példagráf esetén ''P''(''G'',&nbsp;''t'')&nbsp;=&nbsp;''t''(''t''&nbsp;&minus;&nbsp;1)<sup>2</sup>(''t''&nbsp;&minus;&nbsp;2), és valóban,&nbsp;''P''(''G'',&nbsp;4)&nbsp;=&nbsp;72.

A kromatikus polinom minimálisan annyi információt hordoz ''G'' gráf színezhetőségéről, mint a kromatikus szám. Valójában χ az a legkisebb pozitív egész szám, ami nem gyöke a kromatikus polinomnak:
: <math>\chi (G)=\min\{ k\,\colon\,P(G,k) > 0 \}.</math>

Az n csúcsú egyszerű <math>G</math> gráf kromatikus polinomja n-edfokú, egész együtthatós, az együtthatók pedig váltakozó előjelűek (a 0 megengedett az együtthatók között), főegyütthatója 1, [[Konstans (matematika)|konstans]] tagja zérus.

{| class="wikitable"
|+'''Néhány gráf kromatikus polinomja'''
|-
| <math>K_3</math> háromszög || <math>t(t-1)(t-2)</math>
|-
| <math>K_n</math> [[teljes gráf]] || <math>t(t-1)(t-2) \cdots (t-(n-1))</math>
|-
| ''n'' csúcsú [[fagráf]] || <math>t(t-1)^{n-1}</math>
|-
| <math>C_n</math> [[körgráf]] || <math>(t-1)^n+(-1)^n(t-1)</math>
|-
| [[Petersen-gráf]] || <math>t(t-1)(t-2)(t^7-12t^6+67t^5-230t^4+529t^3-814t^2+775t-352)</math>
|}

===Élszínezés===
{{fő|Élszínezés}}
Egy gráf '''élszínezése''' alatt ''éleinek'' jó színezése értendő, olyan színezés tehát, ahol egyetlen csúcs sem illeszkedik két azonos színű élre. A ''k'' színnel történő jó élszínezést ''k''-élszínezésnek nevezik, és ekvivalens az élhalmaz ''k'' [[párosítás]]ra történő szétosztásával (particionálásával). Az a legkisebb ''k'' szám, amire a ''G'' gráfnak van jó ''k''-élszínezése, a gráf '''élkromatikus száma''' vagy '''kromatikus indexe''', amit ''χ''′(''G'')-vel jelölnek. '''Tait-színezésnek''' a [[3-reguláris gráf]]ok 3-élszínezését nevezik. A [[négyszín-tétel]] azzal az állítással ekvivalens, miszerint minden síkbarajzolható 3-reguláris [[elválasztó él|hídmentes]] gráfnak létezik Tait-színezése.

Az élkromatikus szám megegyezik a gráf [[élgráf]]jának kromatikus számával. Nyilvánvaló, hogy az élkromatikus szám nem lehet kisebb a maximális fokszámnál, hiszen az egy pontra illeszkedő éleket mind különböző színekre kell színezni. Viszont egyszerű gráfokra az élkromatikus szám ennél legfeljebb eggyel lehet nagyobb.

===Totális színezés===
{{fő|Totális színezés}}

A '''totális színezés''' során a gráf csúcsaihoz ''és'' éleihez is színeket rendelnek. Ha külön nem jelölik, általában ''jó'' totális színezésről van szó, amikor a gráfnak sem érintkező élei, sem valamely élének végpontjai nem lehetnek azonos színűek. A ''χ″(G)'' totális kromatikus szám a ''G'' totális színezéséhez szükséges legkevesebb szín száma.

== Tulajdonságok ==

===A kromatikus számra vonatkozó korlátok===
Ha minden csúcsot különbözőre színezünk, az mindig jó színezés, ezért:

: <math>1 \le \chi(G) \le n.</math>

Az 1-színezhető gráfok – <math>\chi(G) = 1</math> – pontosan megegyeznek az [[üres gráf|élmentes gráfokkal]], a 2-színezhetőek – <math>\chi(G) = 2</math> – pedig az éllel rendelkező [[páros gráf]]okkal (köztük a [[fa (gráfelmélet)|fákkal]], illetve erdőkkel). <math>\chi(G)</math> <math>\geq</math> <math>3</math> ha <math>G</math> tartalmaz páratlan kört. Az ''n'' csúcsú <math>K_n</math> [[teljes gráf]]ok színezéséhez <math>\chi(K_n)=n</math> színre van szükség. Egy optimális színezésben a gráf ''m''' éle közül legalább egy él húzódik minden színosztály-pár között, ezért:

: <math>\chi(G)(\chi(G)-1) \le 2m.</math>

Ha ''G'' tartalmaz ''k'' méretű [[klikk (gráfelmélet)|klikket]], annak színezéséhez legalább ''k'' színre van szükség – a kromatikus szám tehát legalább akkora, mint az <math>\omega(G)</math> klikkszám:

: <math>\chi(G) \ge \omega(G).</math>

Ez az egyenlőtlenség [[perfekt gráf]]okra (így teljes gráfokra is) éles – ugyanis ha a gráf perfekt <math>\chi(G)</math> = <math>\omega(G)</math> minden feszített részgráfjára – néhány gráfra viszont nagyon rossz becslést ad.

A [[négyszín-tétel]] alapján minden [[síkbarajzolható gráf]] 4-színezhető – <math>\chi(G)\le4</math>.

[[Mohó színezés]]sel megmutatható, hogy minden gráf kiszínezhető maximális [[fokszám (gráfelmélet)|fokszámánál]] legfeljebb 1-gyel több színnel:

: <math>\chi(G) \le \Delta(G) + 1. </math>

Teljes gráfok esetében <math>\chi(G)=n</math> és <math>\Delta(G)=n-1</math>, [[Körgráf|páratlan kör]]ökre pedig <math>\chi(G)=3</math> és <math>\Delta(G)=2</math>, tehát ezekre a gráfokra a korlát a lehető legjobb. Más esetekben kissé javítható; a [[Brooks-tétel]]<ref>{{harvtxt|Brooks|1941}}</ref> szerint:
: <math>\chi (G) \le \Delta (G) </math> a ''G'' összefüggő, egyszerű gráfra, kivéve ha ''G'' teljes gráf vagy páratlan kör.

===A kromatikus számra vonatkozó alsó korlátok===
Az évek során a kromatikus szám több alsó korlátját felfedezték:

'''Hoffman-féle korlát:''' Legyen <math>W</math> valós szimmetrikus mátrix, melyben <math> W_{i,j} = 0 </math> akkor áll fenn, ha <math>(i,j) </math> nem egy él <math>G</math>-ben. Definiáljuk <math>\chi_W(G) = 1 - \tfrac{\lambda_{\max}(W)}{\lambda_{\min}(W)}</math>-t, ahol <math>\lambda_{\max}(W), \lambda_{\min}(W)</math> a <math>W</math> legnagyobb, illetve legkisebb sajátértékei. Legyen továbbá <math> \chi_H(G) = \max_W \chi_W(G)</math>, ahol <math>W</math> az előbbi definíció szerinti. Ekkor:
: <math> \chi_H(G)\leq \chi(G)</math>.

'''Vektorkromatikus szám:''' Legyen <math>W</math> pozitív szemidefinit mátrix, melyben <math> W_{i,j} \le -\tfrac{1}{k-1} </math>, amennyiben <math>(i,j) </math> egy él <math>G</math>-ben. Legyen továbbá <math>\chi_V(G)</math> a legkisebb olyan ''k'', melyre ez a <math>W</math> mátrix létezik. Ekkor:
: <math> \chi_V(G)\leq \chi(G)</math>.

'''[[Lovász-szám]]:''' A [[komplementer gráf]] Lovász-száma a kromatikus szám alsó korlátja egyben:
: <math> \vartheta(\bar{G}) \leq \chi(G)</math>.

'''[[Frakcionális kromatikus szám]]:''' a gráf frakcionális kromatikus száma a kromatikus szám alsó korlátja is:
: <math> \chi_f(G) \leq \chi(G)</math>.

Ezeket a korlátokat így lehet sorba rendezni:
: <math> \chi_H(G) \leq \chi_V(G) \leq \vartheta(\bar{G}) \leq \chi_f(G) \leq \chi(G)</math>.

===Magas kromatikus számú gráfok===
A nagy klikkekkel rendelkező gráfok kromatikus száma mindig magas, de ennek a megfordítása nem általánosan igaz. A [[Grötzsch-gráf]] egy háromszöggel nem rendelkező 4-kromatikus gráf, és a példa a [[Mycielski-konstrukció]] segítségével általánosítható.
: '''Mycielski-tétel''' ({{harvard citations|nb|first=Alexander|last=Zykov|year=1949|authorlink=Alexander Zykov}}, {{harvard citations|nb|first=Jan|last=Mycielski|year=1955|authorlink=Jan Mycielski}}): Tetszőlegesen nagy kromatikus számú háromszögmentes gráfok léteznek. Más megfogalmazásban: minden <math>k\geq 2</math> egész számra létezik olyan <math>G_k</math> gráf, melyre <math>\omega(G_k)=2</math> és <math>\chi(G_k)=k</math>

A Brooks-tétel alapján a magas kromatikus számú gráfoknak magas maximális fokszámmal kell rendelkezniük. További lokális tulajdonság, ami magas kromatikus számhoz vezet, a nagy klikkek jelenléte. A színezhetőség azonban nem teljes mértékben lokális jelenség: egy magas [[girth]]ű gráf lokálisan úgy néz ki, mint egy fa, hiszen az összes kör hosszú, kromatikus száma azonban mégsem feltétlenül 2:
:'''Tétel''' (Erdős): Léteznek tetszőlegesen magas girthparaméterrel és kromatikus számmal rendelkező gráfok.<ref>{{citation | last = Erdős | first = Paul | authorlink = Erdős Pál | journal = Canadian Journal of Mathematics | pages = 34–38 | title = Graph theory and probability | volume = 11 | year = 1959 | doi = 10.4153/CJM-1959-003-9}}.</ref>

===Az élkromatikus számra vonatkozó korlátok===
A ''G'' gráf élszínezése megegyezik <math>L(G)</math> [[élgráf]]jának csúcsszínezésével és viszont. Ezért:

:<math>\chi'(G)=\chi(L(G)).</math>

Szoros összefüggés van az élszínezhetőség és a gráf <math>\Delta(G)</math> maximális fokszáma között. Mivel az ugyanabból a csúcsból kiinduló összes élnek különböző színűnek kell lennie, ezért:

: <math>\chi'(G) \ge \Delta(G).</math>

Továbbá,

: '''[[Kőnig-tétel (gráfelmélet)|Kőnig-tétel]]:''' <math>\chi'(G) = \Delta(G)</math>, ha ''G'' páros gráf.

Általában véve a kapcsolat még erősebb, mint ami a csúcsszínezésre vonatkozó Brooks-tételnél tapasztalható:
: '''[[Vizing-tétel]]:''' a <math>\Delta</math> maximális fokszámú gráf élkromatikus száma (kromatikus indexe) vagy <math>\Delta</math>, vagy <math>\Delta+1</math>.

===Egyéb tulajdonságok===
Egy gráfnak pontosan akkor van ''k''-színezése, ha létezik olyan [[körmentes irányítás]]a, melyben a [[leghosszabb út-probléma|leghosszabb út]] hossza legfeljebb ''k''; ez a [[Gallai–Hasse–Roy–Vitaver-tétel]] {{harv|Nešetřil|Ossona de Mendez|2012}}.

Síkbarajzolható gráfok esetén a csúcsszínezések lényegében a [[sehol sem nulla folyam]]ok duálisai.

Végtelen gráfokról jóval kevesebbet lehet elmondani – néhány eredmény a végtelen gráfok színezésével kapcsolatban:
*Ha egy ''G'' [[végtelen gráf]] minden véges részgráfja ''k''-színezhető, akkor ''G'' is az, ha igaznak fogadjuk el a [[kiválasztási axióma|kiválasztási axiómát]]. Ez a [[De Bruijn–Erdős-tétel (gráfelmélet)|De Bruijn–Erdős-tétel]] {{harvtxt|de Bruijn|Erdős|1951}}.
*Ha egy gráfnak van teljes ''n''-színezése minden ''n'' ≥ ''n''<sub>0</sub>-ra, akkor létezik végtelen teljes színezése {{harv|Fawcett|1978}}.

===Nyitott kérdések===
A fentiek alapján <math> \omega(G) \le \chi(G) \le \Delta(G) + 1. </math> Reed egy 1998-as sejtése szerint a kromatikus szám lényegében az alsó korláthoz esik közelebb:
<math> \chi(G) \le \left\lceil \frac{\omega(G) + \Delta(G) + 1}{2} \right\rceil. </math>

A [[Hadwiger–Nelson-probléma|sík kromatikus száma]], ahol két pont akkor van összekötve, ha éppen egység távolságra vannak, ismeretlen, mindenesetre a 4, 5, 6 és 7 számok valamelyike. További, kromatikus számmal kapcsolatos megoldatlan kérdések közé tartozik a [[Hadwiger-sejtés (gráfelmélet)|Hadwiger-sejtés]], ami szerint a ''k'' kromatikus számú gráfok mindig tartalmazzák a ''k'' csúcsú [[teljes gráf]]ot [[Minor (gráfelmélet)|gráfminor]]ként, az [[Erdős–Faber–Lovász-sejtés]] ami a teljes gráfok páronként pontosan egy közös csúcsot tartalmazó uniójának kromatikus számára állít fel korlátot, valamint az [[Albertson-sejtés]], ami szerint a ''k''-kromatikus gráfok között a teljes gráfoknak a legalacsonyabb a [[Metszési szám (gráfelmélet)|metszési száma]].

Amikor Birkhoff és Lewis a négyszínsejtés megoldásának céljából bevezették a [[kromatikus polinom]]ot, azt a sejtést fogalmazták meg, hogy ''G'' síkbarajzolható gráfok <math>P(G,t)</math> polinomja nem tartalmaz zérushelyet a <math>[4,\infty)</math> régióban. Bár azt már sikerült igazolni, hogy ezen kromatikus polinomoknak nincs zérushelye az <math>[5,\infty)</math> régióban és hogy <math>P(G,4) \neq 0</math>, a sejtés mégis bizonyítatlan. További nyitott kérdés az azonos kromatikus polinommal rendelkező gráfok karakterizációja, valamit annak meghatározása, hogy melyik polinomok lehetnek gráfok kromatikus polinomjai.

==Algoritmusok==

===Polinom idejű algoritmusok===
Annak meghatározása, hogy egy gráf két színnel színezhető-e, ekvivalens a gráf [[páros gráf|párosságának]] tesztelésével, így akár [[szélességi keresés|szélességi]], akár [[mélységi keresés]]sel [[lineáris idő]]ben számítható. Általánosabban, a [[perfekt gráf]]ok kromatikus száma és az ahhoz tartozó színezés [[szemidefinit programozás]]sal [[polinom idő]]ben meghatározható. A [[kromatikus polinom]] zárt alakban is előállítható sok gráftípus esetén, például erdőkre, merev körű gráfokra, körökre, kerékgráfokra és létragráfokra, ezeket így polinom időben ki lehet értékelni.

Ha a gráf síkba rajzolható, és alacsony a [[fafelbontás]]uk szélessége (vagy nem síkba rajzolható, de fafelbontásuk ismert), akkor dinamikus programozással szintén polinom időben színezhetők. Általánosan elmondható, hogy a szükséges idő a gráf méretének polinom, a fafelbontás szélességének viszont exponenciális függvénye.

===Egzakt algoritmusok===
Egy ''k''-színezés [[brute-force keresés]]e a ''k'' szín ''n'' csúcshoz való <math>k^n</math> hozzárendelésének érvényességét vizsgálja. A kromatikus szám, illetve kromatikus polinom kiszámításánál ezt a módszert alkalmazzák minden <math>k=1,\ldots,n-1</math> értékre, ami csak a legkisebb bemeneti gráfoknál használható a gyakorlatban.

[[Dinamikus programozás]]t használva, és a [[maximális független csúcshalmaz]]ok számának korlátját feltételezve a ''k''-színezhetőség <math>O(2,445^n)</math> időben és térben eldönthető.<ref>{{harvtxt|Lawler|1976}}</ref> A [[tartalmazás és kizárás elve|tartalmazás és kizárás elvének]], illetve [[Samuel Yates|Yates]] gyors zéta-transzformációs algoritmusának felhasználásával a ''k''-színezhetőség <math>O(2^nn)</math><ref name="bhk">{{harvtxt|Björklund|Husfeldt|Koivisto|2009}}</ref> időben eldönthető tetszőleges ''k''-ra. Ennél gyorsabb algoritmusok ismertek a 3- és 4-színezhetőségre, melyek <math>O(1,3289^n)</math>,<ref>{{harvtxt|Beigel|Eppstein|2005}}</ref> illetve <math>O(1,7272^n)</math><ref>{{harvtxt|Fomin|Gaspers|Saurabh|2007}}</ref> időben eldönthetők.

===Élösszehúzás===
Egy ''G'' gráf <math>G/uv</math> [[élösszehúzás]]a vagy kontrakciója a ''G''-hez egy olyan gráfot rendel, melyben az <math>u</math> és <math>v</math> közötti éleket elhagyjuk és a két csúcsot egy darab <math>w</math> csúcsban egyesítjük, ami az összes, korábban <math>u</math>-ban vagy <math>v</math>-ben végződő él végpontja lesz. Ez a művelet fontos szerepet játszik a gráfok színezésének vizsgálatában.

A kromatikus szám {{harvtxt|Zykov|1949}} alapján kielégíti az alábbi rekurrencia-relációt:
:<math>\chi(G) = \text{min} \{ \chi(G+uv), \chi(G/uv)\},</math>
ahol ''u'' és ''v'' nem szomszédos csúcsok, <math>G+uv</math> pedig az a gráf, ahol <math>u</math> és <math>v</math> közé egy él be van húzva. Több algoritmus is ennek a rekurziónak a kiszámításán alapszik. A számítás eredményével kapott számítási fát néha Zykov-fának nevezik. A futási idő <math>u</math> és <math>v</math> megválasztásától függ.

A kromatikus polinom az alábbi rekurzív formulát elégíti ki:
:<math>P(G-uv, k)= P(G/uv, k)+ P(G, k),</math>

ahol <math>u</math> és <math>v</math> szomszédos csúcsok <math>G-uv</math> az a gráf, amit az <math>uv</math> él elhagyásával kapunk. <math>P(G - uv, k)</math> az összes lehetséges színezését adja a gráfnak, ahol egy színt használhatunk többször is. A jó színezések száma ezen a módon két gráf színezésének összegeként áll elő: ha <math>u</math> és <math>v</math> különböző színűek, akkor nyugodtan vizsgálhatjuk azt a gráfot, ahol <math>u</math> és <math>v</math> szomszédosak, ha pedig <math>u</math> és <math>v</math> azonos színűek, akkor azt a gráfot vizsgáljuk, ahol az <math>u</math> és <math>v</math> csúcsokat egyesítettük.

Tuttét az iránti érdeklődése, hogy milyen egyéb gráftulajdonságok elégítenek ki hasonló rekurrenciákat, vezette el a kromatikus polinom kétváltozós általánosításának, a [[Tutte-polinom]]nak a felfedezéséhez.

Ezek a kifejezések adtak teret a ''deletion–contraction'', avagy törlés-összevonás algoritmusnak, ami számos gráfszínezési algoritmus alapját képezi. A futásidő megegyezik a [[Fibonacci-számok]] rekurziójának felel meg, így a legrosszabb futási idő esetén az algoritmus <math>\left(\tfrac{1+\sqrt{5}}2\right)^{n+m}=O(1,6180^{n+m})</math> polinom faktorában fut, ahol ''n'' a csúcsok, ''m'' az élek száma.<ref>{{harvtxt|Wilf|1986}}</ref> Az analízis javítható a bemeneti gráf [[feszítőfa|feszítőfáinak]] <math>t(G)</math> számának polinom faktoráig.<<ref>{{harvtxt|Sekine|Imai|Tani|1995}}</ref>
A gyakorlatban [[branch and bound]] („korlátozás és elágazás”) heurisztikák és az izomorfizmusok kiküszöbölése segítségével néhány rekurzív hívás kiküszöbölhető. A futásidő a csúcspár kiválasztásának stratégiáján múlik.

===Mohó színezés===
{{fő|Mohó színezés}}
[[Fájl:Greedy colourings.svg|thumb|right|Ugyanannak a gráfnak két, különböző csúcssorrendet alapul vevő mohó színezése. A jobboldali példa ''n'' csúcsú 2-színezhető gráfokra általánosítható, ahol a mohó algoritmus <math>n/2</math> színt használ fel.]]

A színezés [[mohó algoritmus]]a a csúcsokat specifikus, <math>v_1</math>,…,<math>v_n</math> sorrendben veszi figyelembe, és <math>v_i</math>-hez azt a legkisebb elérhető színt rendeli hozzá, amit <math>v_i</math> szomszédai <math>v_1</math>,…,<math> v_{i-1}</math> között még nem használtak el. Ha nincs ilyen szín, akkor egy új színt rendel hozzá. A kapott színezés minősége a választott sorrendtől függ. Mindig létezik olyan sorrend, ami az optimális, azaz <math>\chi(G)</math> színt használó mohó színezéshez vezet. Másrészt a mohó színezéssel nagyon rossz eredmények is kijöhetnek. Például a két színnel színezhető, ''n'' csúcsú [[Koronagráf (gráfelmélet)|koronagráfok]] esetében a mohó színezés akár <math>n/2</math> színt is felhasználhat.

[[Merev körű gráf]]ok, és annak speciális esetei, az [[intervallumgráf]]ok és [[egység-intervallumgráf]]ok esetében a mohó algoritmussal polinom időben megtalálható az optimális színezés, a csúcsok sorrendjét a gráf [[perfekt eliminációs rendezés]]ének fordítottjának választva. A [[perfekt rendezhető gráf]]ok általánosítják ezt a tulajdonságot, de NP-nehéz ezen gráfok perfekt eliminációs rendezését megtalálni.

Ha a csúcsok [[fokszám (gráfelmélet)|fokszám]] szerint csökkenő sorrendben szerepelnek, a mohó színezés legfeljebb a gráf maximális fokszámánál 1-gyel több színt használ. Ezt a heurisztikát szokták Welsh–Powell-algoritmusnak nevezni.<ref>{{harvtxt|Welsh|Powell|1967}}</ref> A [[Daniel Brélaz|Brélaz]] által alkalmazott heurisztika a sorrendet dinamikusan választja meg, az algoritmus futása közben. Ebben a soron következő lépésnek mindig azt a csúcsot választja, aminek a szomszédai közt a legtöbb fajta szín szerepel.<ref>{{harvtxt|Brélaz|1979}}</ref> Ezeket az algoritmusokat gyűjtőnevükön ''szekvenciális színező algoritmusoknak'' nevezik.

Adott gráf mohó színezése során (a csúcsok sorrendjének legrosszabb megválasztásával) elérhető maximális számú színt a gráf [[Grundy-szám]]-nak nevezik.

===Párhuzamos és elosztott algoritmusok===
<!--Az [[elosztott gráfszínezés]] és a [[Cole–Vishkin-algoritmus]] ebbe a szakaszba irányít át-->
Az [[elosztott algoritmus]]ok területén a gráfszínezés szorosan kapcsolódik a [[szimmetriasértés]] problémájához. Elegendően nagy Δ maximális fokszámú gráfokon a legkorszerűbb véletlen algoritmusok gyorsabban végeznek a determinisztikus algoritmusoknál. A leggyorsabb véletlen algoritmusok a Schneider et al. által kifejlesztett multi-trials technikát („többszörös próba”) használják.<ref name="Schneider 2010">{{harvtxt|Schneider|2010}}</ref>

[[Szimmetrikus gráf]]ban [[determinisztikus algoritmus]] nem képes a jó csúcsszínezést megtalálni. Szükség van valamilyen segédinformációra a szimmetria elrontásához. Egy általános megoldás szerint minden csúcs eredetileg rendelkezik egyedi azonosítóval, például az {1, 2, ..., ''n''} halmazból. Más megközelítésben, feltehetjük, hogy egy ''n''-színezésből indulunk ki. A feladat a szükséges színek számának csökkentése ''n''-ről például Δ&nbsp;+&nbsp;1-re. Minél több felhasználható szín van, például használható fel, például Δ&nbsp;+&nbsp;1 helyett O(Δ), annál kevesebb kommunikációs körre van szükség.<ref name="Schneider 2010"/>

A (Δ&nbsp;+&nbsp;1)-színezés mohó algoritmusának kézenfekvő elosztott változata legrosszabb esetben Θ(''n'') kommunikációs kört igényel − az információnak el kell jutnia a hálózat egyik oldaláról a másikig.

A legegyszerűbb érdekes eset az ''n''-[[körgráf|kör]]. Richard Cole és [[Uzi Vishkin]]<ref>{{harvtxt|Cole|Vishkin|1986}}, lásd még {{harvtxt|Cormen|Leiserson|Rivest|1990|loc = Section 30.5}}</ref> megmutatja, hogy létezik olyan elosztott algoritmus, ami a felhasznált színek számát ''n''-ről ''O''(log&nbsp;''n'')-re csökkenti egyetlen szinkron kommunikációs lépésben. Ugyanezt a műveletet ismételgetve az ''n''-kör 3-színezését ''O''(log*&nbsp;''n'') kommunikációs lépésben el lehet végezni (feltéve, hogy egyedi csomóponti azonosítók vannak).

A log* művelet, avagy az [[iterált logaritmus]] (a [[tetráció]] inverz művelete) egy rendkívül lassan növekvő függvény, „szinte konstans”. Ezért Cole és Vishkin eredménye kapcsán felmerült a kérdés, hogy létezik-e konstans idejű elosztott algoritmus egy ''n''-kör 3-színezésére. {{harvtxt|Linial|1992}} megmutatta, hogy ez nem lehetséges: bármely determinisztikus elosztott algoritmusnak Ω(log*&nbsp;''n'') kommunikációs lépésre van szüksége az ''n''-kör ''n''-színezésének 3-színezésre való redukálásához.

Cole és Vishkin technikáját tetszőleges, korlátos fokszámú gráfokra is alkalmazni lehet; a futási idő poly(Δ) + ''O''(log*&nbsp;''n'').<ref>{{harvtxt|Goldberg|Plotkin|Shannon|1988}}</ref> A technikát Schneider et al. terjesztette ki [[egységkörgráf]]okra<ref>{{harvtxt|Schneider|2008}}</ref> A leggyorsabb, kis Δ értékre (Δ&nbsp;+&nbsp;1)-színezést végző determinisztikus algoritmust Leonid Barenboim, Michael Elkin és Fabian Kuhn jegyzi.<ref>{{harvtxt|Barenboim|Elkin|2009}}; {{harvtxt|Kuhn|2009}}</ref> Barenboim et al. algoritmusa ''O''(Δ)&nbsp;+&nbsp;log*(''n'')/2 időben fut, ami ''n'' tekintetében optimális, mivel az ½ konstans faktor nem javítható Linial alsó korlátja miatt. {{harvtxt|Panconesi|Srinivasan|1996}} hálózati dekompozíciók segítségével talál Δ+1-színezést <math> 2^{O\left(\sqrt{\log n}\right)} </math> időben.

Az élszínezés elosztott modellű problémáját szintén megvizsgálták. {{harvtxt|Panconesi|Rizzi|2001}} (2Δ&nbsp;&minus;&nbsp;1)-színezést végzett ''O''(Δ&nbsp;+&nbsp;log*&nbsp;''n'') időben ezzel a modellel. Az elosztott csúcsszínezés {{harvtxt|Linial|1992}}-féle alsó korlátja az elosztott élszínezési problémára is érvényes.

===Decentralizált algoritmusok===
A decentralizált algoritmusokban az üzenetküldés sem megengedett (ellentétben az elosztott algoritmusokkal, ahol a helyi üzenetküldés fontos szerepet kap). Léteznek hatékony decentralizált algoritmusok, melyek képesek egy gráf jó színezését megtalálni, ha az létezik. Ezek felteszik, hogy egy csúcs képes annak érzékelésére, ha bármelyik szomszédja vele megegyező színt használna, azaz ha egy helyi konfliktus történik. Ez egy több alkalmazásnál előforduló enyhe feltételezés, például a vezeték nélküli hálózatok kiosztásánál általában észszerű feltételezni, hogy egy bázisállomás észreveszi, hogy egy vele interferáló adó ugyanazt a csatornát használja (pl. a SINR, azaz „jel-zaj+interferencia viszony” mérésével). Ez az érzékelési képesség már elegendő ahhoz, hogy a tanuló gépeken alapuló algoritmusok 1 valószínűséggel rátaláljanak egy jó gráfszínezésre.<ref>Pl. lásd {{harvtxt|Leith|Clifford|2006}} és {{harvtxt|Duffy|O'Connell|Sapozhnikov|2008}}.</ref>

===Számítási bonyolultság===
A gráfszínezés egy bonyolult számítási művelet. [[NP-teljes]] nehézségű annak eldöntése, hogy adott gráfnak adott ''k'' értékre létezik-e jó ''k''-csúcsszínezése, kivéve a ''k'' ∈ {0,1,2} eseteket. NP-nehéz feladat a gráf kromatikus számának kiszámítása.<ref>{{harvtxt|Garey|Johnson|Stockmeyer|1974}}; {{harvtxt|Garey|Johnson|1979}}.</ref>
A 3-színezési probléma NP-teljes még 4-reguláris [[síkbarajzolható gráf]]ok esetében is.<ref>{{harvtxt|Dailey|1980}}</ref> Mindazonáltal a ''k'' > 3 értékekre a síkbarajzolható gráfoknak mindig létezik ''k''-színezése, a [[négyszín-tétel]] értelmében, ami polinom időben meg is található.

A legjobb ismert [[approximációs algoritmus]] a kromatikus szám O(''n''(log&nbsp;log&nbsp;''n'')<sup>2</sup>(log&nbsp;n)<sup>−3</sup>) faktorában számol színezést.<ref>{{harvtxt|Halldórsson|1993}}</ref> Tetszőleges ''ε''&nbsp;>&nbsp;0-ra a kromatikus szám ''n''<sup>1&minus;''ε''</sup>-n belüli approximációja [[NP-nehéz]].<ref>{{harvtxt|Zuckerman|2007}}</ref>

Szintén NP-nehéz egy 3-színezhető gráf 4-színezését megtalálni,<ref>{{harvtxt|Guruswami|Khanna|2000}}</ref> vagy egy ''k''-színezhető gráfot ''k''<sup>(log ''k''&nbsp;)&nbsp;/&nbsp;25</sup> színnel kiszínezni [[elegendően nagy]] ''k'' konstansra.<ref>{{harvtxt|Khot|2001}}</ref>

A kromatikus polinom együtthatóinak kiszámítása [[Sharp-P-teljes|#P-nehéz]]. Valójában még a <math>\chi(G,k)</math> értékének kiszámítása bármely ''k'' [[racionális pont]]on is #P-nehéz, kivéve a ''k''&nbsp;=&nbsp;1 és ''k''&nbsp;=&nbsp;2 esetet.<ref>{{harvtxt|Jaeger|Vertigan|Welsh|1990}}</ref> Nem létezik [[polinomiális approximációs séma|FPRAS (teljesen polinom idejű randomizált approximációs séma)]] a kromatikus polinom kiszámítására bármely ''k''&nbsp;≥&nbsp;1,5 racionális ponton, a ''k''&nbsp;=&nbsp;2 esetet kivéve – hacsak nem igaz az, hogy [[NP (bonyolultság)|NP]]&nbsp;=&nbsp;[[RP (bonyolultság)|RP]].<ref>{{harvtxt|Goldberg|Jerrum|2008}}</ref>

Élszínezés Vizing eredményének bizonyítása meg is ad egy legfeljebb Δ+1 színt használó algoritmust. Annak eldöntése azonban, hogy az élkromatikus szám a két szóba jövő érték közül melyik, NP-teljes.<ref>{{harvtxt|Holyer|1981}}</ref> Approximációs algoritmusok tekintetében a Vizing-féle algoritmusból látható, hogy az élkromatikus szám 4/3-ra közelíthető, és a bonyolultsági eredmények azt mutatják, hogy semmilyen ''ε&nbsp;>&nbsp;0'' értékre nem létezik (4/3&nbsp;&minus;&nbsp;''ε''&nbsp;)-algoritmus, kivéve, ha [[P&nbsp;=&nbsp;NP]]. Ezek az approximációs algoritmusok között a legrégebbi eredmények közé tartoznak, bár egyik cikkben sem jelennek meg explicit módon.<ref>{{harvtxt|Crescenzi|Kann|1998}}</ref>

==Alkalmazások==

===Ütemezés===
A csúcsszínezés több [[ütemezés]]i probléma modelljének tekinthető.<ref>{{harvtxt|Marx|2004}}</ref> Legtisztább formájában feladatok adott halmazához időréseket kell rendelni, minden feladat egy időrést foglal el. A feladatok tetszőleges sorrendben végrehajthatók, de egyes feladatpárok ''konfliktusban'' lehetnek egymással, például mert ugyanazt a közös erőforrást (munkaerőt, helyiséget stb.) használják. Az ennek megfelelő gráf minden csúcsa egy-egy feladatnak felel meg, a konfliktusban lévő feladatok között húzódik él. A gráf kromatikus száma megegyezik a minimális ''teljes átfutási idővel'', a feladatok konfliktusmentes végrehajtásának optimális idejével.

Az ütemezési probléma részletei határozzák meg a gráf szerkezetét. Ha például az egyes járatokhoz kell hozzárendelni repülőgépeket, a kapott konfliktusgráf egy [[intervallumgráf]], aminek a színezése hatékonyan megoldható. Ha rádióállomások sávszélesség-kiosztását tekintjük, a kapott konfliktusgráf [[egységkörgráf]], melynek színezése 3-approximálható.

===Regiszterallokáció===
{{fő|Regiszterallokáció}}

A [[fordítóprogram]]ok olyan [[Program (informatika)|számítógépes programok]], melyek az egyik számítógépes nyelvről a másikra fordítanak. Az eredményül kapott kód futási idejének javítására szolgáló [[optimalizáló fordító|optimalizálási]] technikák egyike a [[regiszterallokáció]], ahol a lefordított program leggyakrabban használt értékeit a processzor által gyorsan elérhető [[Regiszter (számítástechnika)|regiszterekben]] tárolják. Ideális esetben az értékadások és az értékekkel való műveletek is a (korlátozott számú) regiszterek valamelyikében történnek.

A tankönyvi megoldás a probléma gráfszínezésként történő modellezése.<ref>{{harvtxt|Chaitin|1982}}</ref> A fordító ún. interferenciagráfot ''(interference graph)'' konstruál, melynek csúcsai a változók, és két csúcsot akkor köt össze él, ha a hozzájuk tartozó változókra azonos időben van szükség. Ha a gráf ''k'' színnel színezhető, akkor azokat a változókat, amikre a programnak azonos időben van szüksége, ''k'' regiszterben el lehet tárolni.

===Egyéb alkalmazások===
A gráfszínezés problémája számos gyakorlati területen felmerül, ilyenek például a [[mintaillesztés]], sportesemények lebonyolítási rendjének meghatározása, ülésrendek, vizsgák időbeosztásának, taxik menetrendjének összeállítása, [[szúdoku]] rejtvények megoldása.<ref name="Lewis2015">Lewis, R. ''A Guide to Graph Colouring: Algorithms and Applications''. Springer International Publishers, 2015.</ref>

==Egyéb színezések==
===[[Ramsey]]-elmélet===
{{bővebben|Ramsey-tétel}}
A „nem megfelelő színezések” egy fontos területét a Ramsey-elmélet tanulmányozza. A Ramsey-elmélet Frank Plumpton Ramsey [[matematikus]]–[[Közgazdaságtan|közgazdász]] harmincas években publikált eredménye által elindított igen fontos ága a [[kombinatorika|kombinatorikának]] és a gráfelméletnek.
Az elméletet összefűző filozófiát nagyon egyszerűen meg lehet fogalmazni: Ha egy [[matematikai struktúra|struktúra]] hatalmas, akkor az nem kerülheti el az igen szabályos nagy részstruktúrákat.

Ennek egyik része, hogy a gráf éleihez rendelünk színeket és nincs megkötés a közös csúcsban találkozó élek színére. A [[Ramsey-tétel]] legegyszerűbb esete: a <math>K_6</math> éleit tetszőlegesen megszínezve két színnel biztosan keletkezik benne egyszínű háromszög.

===Egyéb színezések===
{{Col-begin}}
{{Col-break}}
; [[Aciklikus színezés]]: bármely két szín által meghatározott részgráf körmentes
; [[AVD-totális színezés]]: szomszédos csúcsokat megkülönböztető totális színezés
; [[B-színezés]]: a csúcsok olyan színezése, ahol minden színosztályhoz található olyan csúcs, aminek létezik szomszédja az összes többi színosztályból
; [[Csillagszínezés]]: bármely két szín által meghatározott feszített részgráf [[csillaggráf]]ok diszjunkt uniója
; [[Defektív színezés]]: olyan, nem feltétlen jó színezés, ahol minden színosztályhoz korlátos fokszámú feszített részgráf tartozik
; [[Egzakt színezés]]: minden színpár ''pontosan'' egy élen jelenik meg
; [[Erős színezés]]: az azonos méretű partíciókban minden szín pontosan egyszer jelenik meg
; [[Erős élszínezés]]: az élek úgy vannak színezve, hogy minden színosztály egy párosítást indukál (megegyezik az élgráf négyzetének színezésével)
; [[Egyenletes színezés]]: a színosztályok mérete legfeljebb eggyel tér el egymástól
; [[Frakcionális színezés]]{{wd|Q5477527}} (tört színezés): egy csúcspont egyszerre többszínű is lehet, az egyes színeknek valamilyen súlyozása van 0 és 1 között, de összegük <1
; [[Gyenge színezés]]: nem jó színezés, ahol minden nem izolált csúcsnak van legalább egy különböző színű csomszédja
; [[Harmonikus színezés]]: minden színpár ''legfeljebb'' egy élen jelenik meg
; [[Egyszínű háromszög|Háromszögmentes élszínezés]]: az élek olyan színezése, ahol minden színosztály [[háromszögmentes gráf|háromszögmentes]] részgráfot alkot
; [[Incidenciaszínezés]]: minden csúcs-él incidenciánál (illeszkedésnél) a csúcsnak és az élnek különböző színűnek kell lennie
; [[Intervallum-élszínezés]]: egy közös csúcsban találkozó élek színeinek (címkéinek) folytonosnak kell lennie
{{Col-break}}
; [[Ívszínezés]]
; [[Komplementer színezés]]: a csúcsok olyan (nem jó) színezése, ahol a színosztályok vagy klikket, vagy független csúcshalmazt feszítenek ki
; [[Körkörös színezés]]: olyan feladatrendszerek motiválják, melyben a feldolgozás ciklikusan halad
; [[Fa mélysége|Középpontos színezés]]: minden összefüggő [[feszített részgráf]]ban van pontosan egyszer felhasznált szín
; [[L(h, k)-színezés]]: a szomszédos csúcsok színeinek távolsága legalább ''h'', a 2 távolságra lévő csúcsok színeinek távolsága legalább ''k''. A h=1 és k=0 eset megegyezik a normál csúcsszínezéssel.
; [[Listaszínezés]]: minden csúcshoz egy listáról választunk ki egy színt
; [[Lista-élszínezés]]: minden élhez egy listáról választunk ki egy színt
; [[Megkülönböztető színezés]]: a csúcsok olyan (nem jó) színezése, ami a gráf összes szimmetriáját megszünteti
; [[Multiszínezés]]: minden csúcsra adott egy szám, ennyi színt kell neki adni úgy, hogy szomszédos színhalmazok diszjunktak legyenek
; [[Orientált színezés]]: figyelembe veszi a gráf éleinek orientációját is
; [[Összegszínezés]]: cél a színek összegének minimalizálása
; [[Rádiószínezés]]: a csúcsok távolságának és a színeik közötti különbségnek az összege nagyobb mint k+1, ahol k pozitív egész szám.
; [[Rangszínezés]]: ha két csúcs ugyanabba az ''i'' színosztályba tartozik, akkor minden köztük lévő útnak tartalmaznia kell ''i''-nél magasabb színű csúcsot
; [[Részszínezés]]: a csúcsok olyan (nem jó) színezése, ahol a színosztályok klikkek diszjunkt unióját feszítik ki
; [[T-színezés]]: két szomszédos csúcs különbségének abszolút értéke nem tartozhat a rögzített ''T'' halmazhoz
; [[Teljes színezés]]: minden színpár legalább egy élen megjelenik
; [[Totális színezés]]: minden él és minden csúcs színezve van
; [[Útszínezés]]: útválasztási problémát modellez a gráfban
{{col-end}}

A színezési probléma [[előjeles gráf]]okra is értelmezhető.

==Források==
* Katona, Recski, Szabó "A számítástudomány alapjai." Typotex. Budapest, 2006.
* [http://www.math.unideb.hu/~turjanyi/Komb_j/K_Win_Doc/g0607.doc] {{Wayback|url=http://www.math.unideb.hu/~turjanyi/Komb_j/K_Win_Doc/g0607.doc |date=20120310214851 }}
* [http://www.math.klte.hu/~turjanyi/eloadasvazlatok2004majus/g409apr13.doc]
* [http://www.cs.bme.hu/~dmarx/papers/marx-neumann-slides.pdf Gráfszínezési problémák és ütemezési alkalmazásaik]
* [http://turul.banki.hu/wp-content/uploads/2008/10/grafelmelet.pdf Gráfelmélet]{{Halott link|url=http://turul.banki.hu/wp-content/uploads/2008/10/grafelmelet.pdf |date=2018-11 }}

==Irodalom==
{{refbegin|2}}
* {{Citation
 | last1=Barenboim | first1=L.
 | last2=Elkin | first2=M.
 | contribution=Distributed (Δ&nbsp;+&nbsp;1)-coloring in linear (in Δ) time
 | pages=111–120
 | title=Proceedings of the 41st [[Symposium on Theory of Computing]]
 | year=2009
 | doi=10.1145/1536414.1536432
 | isbn=978-1-60558-506-2
}}
* {{Citation
| last1= Beigel | first1= R.
| last2= Eppstein | first2= D. | authorlink2= David Eppstein
| title= 3-coloring in time O(1.3289<sup>n</sup>)
| journal= [[Journal of Algorithms]]
| volume= 54
| pages=168–204
| year=2005 | issue= 2)
| doi= 10.1016/j.jalgor.2004.06.008
}}
* {{Citation
 | last1=Björklund | first1=A.
 | last2=Husfeldt | first2=T.
 | last3=Koivisto | first3=M.
 | journal=[[SIAM Journal on Computing]]
 | pages=546–563
 | title=Set partitioning via inclusion–exclusion
 | volume= 39
 | year=2009
 | doi=10.1137/070683933| issue=2
}}
* {{Citation
 | last = Brélaz | first = D. | authorlink = Daniel Brélaz
 | title = New methods to color the vertices of a graph
 | journal = [[Communications of the ACM]]
 | volume = 22
 | year = 1979
 | pages = 251–256
 | doi = 10.1145/359094.359101
 | issue = 4
}}
* {{Citation
 | last = Brooks | first = R. L. | authorlink = R. Leonard Brooks
 | title = On colouring the nodes of a network
 | journal = [[Proceedings of the Cambridge Philosophical Society]]
 | volume = 37
 | year = 1941
 | pages = 194–197
 | doi = 10.1017/S030500410002168X
 | issue = 2
}}
* {{Citation
 | last1 = de Bruijn
 | first1 = N. G.
 | authorlink1 = Nicolaas Govert de Bruijn
 | last2 = Erdős
 | first2 = P.
 | authorlink2 = Erdős Pál
 | title = A colour problem for infinite graphs and a problem in the theory of relations
 | journal = Nederl. Akad. Wetensch. Proc. Ser. A
 | volume = 54
 | year = 1951
 | pages = 371–373
 | url = http://www.math-inst.hu/~p_erdos/1951-01.pdf
 | accessdate = 2018-04-15
 | archívurl = https://web.archive.org/web/20160310003706/http://www.math-inst.hu/~p_erdos/1951-01.pdf
 | archívdátum = 2016-03-10
 }} (= ''Indag. Math.'' '''13''')
* {{Citation
|last=Byskov|first=J.M.
|title=Enumerating maximal independent sets with applications to graph colouring
|journal=Operations Research Letters
|pages=547–556
|volume=32
|year= 2004
|doi=10.1016/j.orl.2004.03.002
|issue=6
}}

* {{Citation
 | last = Chaitin | first = G. J.
 | contribution = Register allocation & spilling via graph colouring
 | title = Proc. 1982 [[SIGPLAN Symposium on Compiler Construction]]
 | year = 1982
 | pages = 98–105
 | doi = 10.1145/800230.806984
 | isbn = 0-89791-074-5
}}
* {{Citation
 | last1 = Cole | first1 = R.
 | last2 = Vishkin | first2 = U.
 | year = 1986
 | title = Deterministic coin tossing with applications to optimal parallel list ranking
 | journal = [[Information and Control]]
 | volume = 70
 | issue = 1
 | pages = 32–53
 | doi = 10.1016/S0019-9958(86)80023-7
}}
* {{Citation
 | last1 = Cormen | first1 = T. H.
 | last2 = Leiserson | first2 = C. E.
 | last3 = Rivest | first3 = R. L.
 | title = [[Introduction to Algorithms]]
 | publisher = The MIT Press
 | year = 1990
 | edition = 1st
}}
* {{Citation
 | last1 = Crescenzi | first1 = P.
 | last2 = Kann | first2 = V.
 | title = How to find the best approximation results — a follow-up to Garey and Johnson
 | journal = [[ACM SIGACT News]]
 | date = December 1998
 | doi = 10.1145/306198.306210
 | volume = 29
 | page = 90
 | issue = 4
}}
* {{Citation
 | last1 = Dailey | first1 = D. P.
 | title = Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
 | journal = [[Discrete Mathematics]]
 | volume = 30
 | pages = 289–293
 | year = 1980
 | doi = 10.1016/0012-365X(80)90236-8
 | issue = 3
}}
* {{Citation
| last1 = Duffy | first1 = K.
| last2 = O'Connell | first2 = N.
| last3 = Sapozhnikov | first3 = A.
| title=Complexity analysis of a decentralised graph colouring algorithm
| journal=Information Processing Letters
| volume=107
| pages=60–63
| year=2008
| url=http://www.hamilton.ie/ken_duffy/Downloads/cfl.pdf
| doi=10.1016/j.ipl.2008.01.002
| issue = 2
}}
* {{Citation
 | last1 = Fawcett | first1 = B. W.
 | title = On infinite full colourings of graphs
 | journal = [[Canadian Journal of Mathematics|Can. J. Math.]]
 | volume = 30
 | pages = 455–457
 | year = 1978
 | doi =10.4153/cjm-1978-039-8
}}

* {{Citation
 | last1 = Fomin | first1 = F.V. | author1-link = Fedor Fomin
 | last2 = Gaspers | first2 = S.
 | last3 = Saurabh | first3 = S.
 | contribution = Improved Exact Algorithms for Counting 3- and 4-Colorings
 | title = Proc. 13th Annual International Conference, COCOON 2007
 | series = [[Lecture Notes in Computer Science]]
 | volume = 4598
 | publisher = Springer
 | year = 2007
 | pages = 65–74
 | doi = 10.1007/978-3-540-73545-8_9
 | isbn=978-3-540-73544-1
}}
* {{Citation
 | last1 = Garey | first1 = M. R. | authorlink1 = Michael R. Garey
 | last2 = Johnson | first2 = D. S. | authorlink2 = David S. Johnson
 | year = 1979
 | title = [[Computers and Intractability: A Guide to the Theory of NP-Completeness]]
 | publisher = W.H. Freeman
 | isbn = 0-7167-1045-5
}}
* {{Citation
 | last1 = Garey | first1 = M. R. | authorlink1 = Michael R. Garey
 | last2 = Johnson | first2 = D. S. | authorlink2 = David S. Johnson
 | last3 = Stockmeyer | first3 = L. | authorlink3 = Larry Stockmeyer
 | year = 1974
 | contribution = Some simplified NP-complete problems
 | url = http://portal.acm.org/citation.cfm?id=803884
 | title = Proceedings of the Sixth Annual ACM Symposium on Theory of Computing
 | pages = 47–63
 | doi = 10.1145/800119.803884
}}
* {{Citation
 | last1 = Goldberg | first1 = L. A. | author1-link = Leslie Ann Goldberg
 | last2 = Jerrum | first2 = M. | authorlink2 = Mark Jerrum
 | title = Inapproximability of the Tutte polynomial
 | journal = [[Information and Computation]]
 | volume = 206
 | issue= 7
 | date= July 2008
 | pages = 908–929
 | doi = 10.1016/j.ic.2008.04.003
}}
* {{Citation
 | last1 = Goldberg | first1 = A. V. | author1-link = Andrew V. Goldberg
 | last2 = Plotkin | first2 = S. A.
 | last3 = Shannon | first3 = G. E.
 | year = 1988
 | title = Parallel symmetry-breaking in sparse graphs
 | journal = [[SIAM Journal on Discrete Mathematics]]
 | volume = 1
 | issue = 4
 | pages = 434–446
 | doi = 10.1137/0401044
}}
* {{Citation
 | last1 = Guruswami | first1 = V.
 | last2 = Khanna | first2 = S.
 | contribution = On the hardness of 4-coloring a 3-colorable graph
 | title = Proceedings of the 15th Annual IEEE Conference on Computational Complexity
 | pages = 188–197
 | year = 2000
 | doi = 10.1109/CCC.2000.856749
 | isbn = 0-7695-0674-7
}}
* {{Citation
 | last = Halldórsson | first = M. M.
 | year = 1993
 | title = A still better performance guarantee for approximate graph coloring
 | journal = Information Processing Letters
 | volume = 45
 | pages = 19–23
 | doi = 10.1016/0020-0190(93)90246-6
}}
* {{Citation
 | last = Holyer | first = I.
 | year = 1981
 | title = The NP-completeness of edge-coloring
 | journal = [[SIAM Journal on Computing]]
 | volume = 10
 | pages = 718–720
 | doi = 10.1137/0210055
 | issue = 4
}}
* {{Citation
 | last1 = Jaeger | first1 = F.
 | last2 = Vertigan | first2 = D. L.
 | last3 = Welsh | first3 = D. J. A.
 | year = 1990
 | title = On the computational complexity of the Jones and Tutte polynomials
 | journal = [[Mathematical Proceedings of the Cambridge Philosophical Society]]
 | volume = 108
 | pages = 35–53
 | doi = 10.1017/S0305004100068936
}}
* {{Citation
 | last1 = Jensen | first1 = T. R.
 | last2 = Toft | first2 = B.
 | title = Graph Coloring Problems
 | publisher = Wiley-Interscience, New York
 | year = 1995
 | isbn = 0-471-02865-7
}}
* {{Citation
 | last = Khot | first = S. |authorlink = Subhash Khot | year = 2001
 | contribution = Improved inapproximability results for MaxClique, chromatic number and approximate graph coloring
 | title = Proc. 42nd Annual [[Symposium on Foundations of Computer Science]]
 | pages = 600–609
 | doi = 10.1109/SFCS.2001.959936
 | isbn = 0-7695-1116-3
}}
* {{Citation
 | last1 = Kubale | first1 = M.
 | title = Graph Colorings
 | publisher = American Mathematical Society
 | year = 2004
 | isbn = 0-8218-3458-4
}}
* {{Citation
 | last1=Kuhn | first1=F.
 | contribution=Weak graph colorings: distributed algorithms and applications
 | pages=138–144
 | title=Proceedings of the 21st [[Symposium on Parallelism in Algorithms and Architectures]]
 | year=2009
 | doi=10.1145/1583991.1584032
 | isbn=978-1-60558-606-9
}}
* {{Citation
 | last1=Lawler | first1=E.L. | authorlink = Eugene Lawler
 | title=A note on the complexity of the chromatic number problem
 | pages=66–67
 | journal=[[Information Processing Letters]]
 | year=1976
|volume= 5
 | doi=10.1016/0020-0190(76)90065-X| issue=3
}}
* {{Citation
 | last1 = Leith | first1 = D.J.
 | last2 = Clifford | first2 = P.
 | year = 2006
 | contribution = A Self-Managed Distributed Channel Selection Algorithm for WLAN
 | title = Proc. RAWNET 2006, Boston, MA
 | url = http://www.hamilton.ie/peterc/downloads/rawnet06.pdf
 | accessdate = 2016-03-03
}}
* {{Citation
 | last1 = Linial | first1 = N. | authorlink = Nati Linial
 | year = 1992
 | title = Locality in distributed graph algorithms
 | journal = [[SIAM Journal on Computing]]
 | volume = 21
 | issue = 1
 | pages = 193–201
 | doi = 10.1137/0221015
}}
* {{Citation
 | last1 = van Lint| first1 = J. H.
 | last2 = Wilson | first2 = R. M.
 | title = A Course in Combinatorics
 | year = 2001
 | edition = 2nd
 | publisher = Cambridge University Press
 | isbn = 0-521-80340-3
}}
* {{Citation
 | last = Marx | first = Dániel
 | contribution = Graph colouring problems and their applications in scheduling
 | title = Periodica Polytechnica, Electrical Engineering
 | year = 2004
 | pages = 11–16
 | volume = 48
 |issue=1–2
 | citeseerx = 10.1.1.95.4268
}}
*{{citation
 | last = Mycielski | first = J. | author-link = Jan Mycielski
 | journal = Colloq. Math.
 | pages = 161–162
 | title = Sur le coloriage des graphes
 | url = http://matwbn.icm.edu.pl/ksiazki/cm/cm3/cm3119.pdf
 | volume = 3
 | year = 1955}}.
*{{citation
 | last1 = Nešetřil | first1 = Jaroslav | author1-link = Jaroslav Nešetřil
 | last2 = Ossona de Mendez | first2 = Patrice | author2-link = Patrice Ossona de Mendez
 | contribution = Theorem 3.13
 | doi = 10.1007/978-3-642-27875-4
 | isbn = 978-3-642-27874-7
 | location = Heidelberg
 | mr = 2920058
 | page = 42
 | publisher = Springer
 | series = Algorithms and Combinatorics
 | title = Sparsity: Graphs, Structures, and Algorithms
 | volume = 28
 | year = 2012}}.
*{{Citation
 | last1=Panconesi
 | first1=Alessandro
 | last2=Rizzi
 | first2=Romeo
 | title=Some simple distributed algorithms for sparse networks
 | publisher=[[Springer-Verlag]]
 | location=Berlin, New York
 | year=2001
 | journal=Distributed Computing
 | issn=0178-2770
 | volume=14
 | issue=2
 | pages=97–100
 | doi=10.1007/PL00008932
}}
* {{Citation
 | last1=Panconesi | first1=A.
 | last2=Srinivasan | first2=A.
 | contribution=On the complexity of distributed network decomposition
 | title=Journal of Algorithms
 | volume= 20
 | year=1996
}}
* {{Citation
 | last1 = Sekine | first1 = K.
 | last2 = Imai | first2 = H.
 | last3 = Tani | first3 = S.
 | contribution = Computing the Tutte polynomial of a graph of moderate size
 | title = Proc. 6th International Symposium on Algorithms and Computation (ISAAC 1995)
 | series = [[Lecture Notes in Computer Science]]
 | volume = 1004
 | publisher = Springer
 | year = 1995
 | pages = 224–233
 | doi = 10.1007/BFb0015427
 | isbn = 3-540-60573-8
}}
* {{Citation
 | last1=Schneider | first1=J.
 | contribution=A new technique for distributed symmetry breaking
 | title=Proceedings of the [[Symposium on Principles of Distributed Computing]]
 | year=2010
 | contribution-url = http://www.dcg.ethz.ch/publications/podcfp107_schneider_188.pdf
}}
* {{Citation
 | last1=Schneider | first1=J.
 | contribution=A log-star distributed maximal independent set algorithm for growth-bounded graphs
 | title=Proceedings of the [[Symposium on Principles of Distributed Computing]]
 | year=2008
 | contribution-url = http://www.dcg.ethz.ch/publications/podc08SW.pdf
}}
* {{Citation
 | last1 = Welsh | first1 = D. J. A.
 | last2 = Powell | first2 = M. B.
 | year = 1967
 | title = An upper bound for the chromatic number of a graph and its application to timetabling problems
 | journal = The Computer Journal
 | volume = 10
 | doi = 10.1093/comjnl/10.1.85
 | pages = 85–86
 | issue= 1
}}
* {{Citation
 | last = West
 | first = D. B.
 | title = Introduction to Graph Theory
 | year = 1996
 | publisher = Prentice-Hall
 | isbn = 0-13-227828-6
}}
* {{Citation
 | last = Wilf | first = H. S.
 | title = Algorithms and Complexity
 | publisher = Prentice–Hall
 | year = 1986
}}
* {{Citation
 | last = Zuckerman | first = D.
 | title = Linear degree extractors and the inapproximability of Max Clique and Chromatic Number
 | journal = [[Theory of Computing (journal)|Theory of Computing]]
 | volume = 3
 | pages = 103–128
 | year = 2007
 | doi = 10.4086/toc.2007.v003a006
}}
* {{citation
 | last = Zykov | first = A. A.
 | issue = 66
 | journal = Mat. Sbornik N.S.
 | language = Russian
 | mr = 0035428
 | pages = 163–188
 | title = О некоторых свойствах линейных комплексов
 | trans-title = On some properties of linear complexes
 | url = http://mi.mathnet.ru/msb5974
 | volume = 24
 | year = 1949}}. Translated into English in ''Amer. Math. Soc. Translation'', 1952, {{MR|0051516}}.
{{refend}}

==Jegyzetek==
{{jegyzetek}}

[[Kategória:Gráfok színezése| ]]
[[Kategória:Számítási problémák a gráfelméletben]]
[[Kategória:Gráfok kiterjesztései és általánosításai]]