A matematika, azon belül a gráfelmélet területén a gráfok 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ése, ha pedig a csúcsok és az élek is színezésre kerülnek, totális színezésrő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áfjának, totális színezése totális gráfjának, síkgráf tartományszínezése pedig 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épek 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 á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
Az első gráfszínezési eredmények síkbarajzolható gráfokkal 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 Hamiltonnal. 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ételt 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épre alapozott bizonyítás.
1912-ben George David Birkhoff vezette be a kromatikus polinomot 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óprogramok regiszter-allokációja 1981-ben került bevezetésre.
Definíció és terminológia 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.
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 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úcshalmazt 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
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 + 4⋅12 = 72-féleképpen lehetséges a színezés: mind a négy színt felhasználva 4! = 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:
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, 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 polinomja. A példagráf esetén P(G, t) = t(t − 1)2(t − 2), és valóban, P(G, 4) = 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:
Az n csúcsú egyszerű 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 tagja zérus.
+Néhány gráf kromatikus polinomja háromszög teljes gráf n csúcsú fagráf körgráf Petersen-grá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ásra 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áfok 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 hídmentes gráfnak létezik Tait-színezése.
Az élkromatikus szám megegyezik a gráf élgráfjá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
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:
Az 1-színezhető gráfok – – pontosan megegyeznek az élmentes gráfokkal, a 2-színezhetőek – – pedig az éllel rendelkező páros gráfokkal (köztük a fákkal, illetve erdőkkel). ha tartalmaz páratlan kört. Az n csúcsú teljes gráfok színezéséhez 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:
Ha G tartalmaz k méretű 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 klikkszám:
Ez az egyenlőtlenség perfekt gráfokra (így teljes gráfokra is) éles – ugyanis ha a gráf perfekt = 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ő – .
Mohó színezéssel megmutatható, hogy minden gráf kiszínezhető maximális fokszámánál legfeljebb 1-gyel több színnel:
Teljes gráfok esetében és , páratlan körökre pedig és , tehát ezekre a gráfokra a korlát a lehető legjobb. Más esetekben kissé javítható; a Brooks-tétel szerint: 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 valós szimmetrikus mátrix, melyben akkor áll fenn, ha nem egy él -ben. Definiáljuk -t, ahol a legnagyobb, illetve legkisebb sajátértékei. Legyen továbbá , ahol az előbbi definíció szerinti. Ekkor: .
Vektorkromatikus szám: Legyen pozitív szemidefinit mátrix, melyben , amennyiben egy él -ben. Legyen továbbá a legkisebb olyan k, melyre ez a mátrix létezik. Ekkor: .
Lovász-szám: A komplementer gráf Lovász-száma a kromatikus szám alsó korlátja egyben: .
Frakcionális kromatikus szám: a gráf frakcionális kromatikus száma a kromatikus szám alsó korlátja is: .
Ezeket a korlátokat így lehet sorba rendezni: .
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 (, ): Tetszőlegesen nagy kromatikus számú háromszögmentes gráfok léteznek. Más megfogalmazásban: minden egész számra létezik olyan gráf, melyre és
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..
Az élkromatikus számra vonatkozó korlátok A G gráf élszínezése megegyezik élgráfjának csúcsszínezésével és viszont. Ezért: