A matematika, azon belül a gráfelmélet területén egy gráf élszínezése során színeket rendelnek hozzá a gráf éleihez. Általában jó élszínezésekkel foglalkoznak, melyek során az ugyanabból a csúcsból kiinduló élek mindig különböző színűek. Például a jobb oldali ábrán látható élszínezés három színt (piros, kék, zöld) használ. Az élszínezés a gráfok lehetséges színezéseinek csak egyetlen típusa.
Az élszínezési probléma azt vizsgálja, hogy jól színezhetők-e adott gráf élei legfeljebb különböző színnel, adott -ra, illetve a lehető legkevesebb szín felhasználásával. Az adott gráf éleihez szükséges minimális színek számát a gráf élkromatikus számának vagy kromatikus indexének nevezik. Az illusztráción látható gráf élei kiszínezhetők három színnel, de kettővel nem, ezért a gráf élkromatikus száma három.
A Vizing-tétel értelmében az egyszerű gráf élszínezéséhez szükséges színek száma vagy a maximális fokszáma, vagy . Egyes gráfok esetében, mint a páros gráfok vagy magas fokszámú síkbarajzolható gráfok, a kromatikus index mindig , multigráfok esetén pedig akár is lehet. Léteznek polinom idejű algoritmusok páros gráfok optimális színezésének, illetve nem páros egyszerű gráfok legfeljebb -színezésének előállítására; az optimális élszínezés általános esetben azonban NP-nehéz feladat és a legjobb ismert algoritmusok is exponenciális idejűek. Az élszínezési problémának számos olyan változatát tanulmányozták, ahol a színek hozzárendelésekor a szomszédosság elkerülése mellett egyéb feltételeknek is teljesülniük kell. Az élszínezések gyakorlati szerepet kapnak az ütemezési problémákban és az optikai hálózatok frekvenciakiosztásában.
Példák Egy páros hosszúságú körgráf élei két színnel kiszínezhetők, egyszerűen a két színt váltakozva kell a kör éleihez hozzárendelni. Ha azonban a kör páratlan hosszúságú, egy harmadik színre is szükség van., problem 16.4, p. 133.
Egy teljes gráf -élszínezhető, amennyiben páros; ez a Baranyai-tétel speciális esete. a következő geometriai konstrukciót adja a színezésre: helyezzünk el pontot egy -oldalú szabályos sokszög csúcsaiba és középpontjába. Minden színosztályhoz adjunk hozzá egy a középpontból a sokszög valamely csúcsába menő élt, és a rá merőleges éleket. Ha azonban páratlan, színre van szükség: az egyes színek csak élhez tartozhatnak, az összes él részéhez., problem 16.5, p. 133. Az, hogy vagy , vagy színre van szükség, a Vizing-tétel következménye.
Több szerző tanulmányozta a páratlan gráfok élszínezéseit. A páratlan gráfok olyan -reguláris gráfok, melyeknek csúcsai méretű játékoshalmazból kiválasztott játékost jelképez, és melyek élei ezen csapatok összes lehetséges párosítását jelképezi (ahol egy játékos páratlan marad, ő a döntőbíró). Az esetnek a jól ismert Petersen-gráf felel meg. az esetre úgy írja le a problémát, hogy a játékosok olyan időbeosztást keresnek a párosításokhoz, hogy minden csapat az összesen hat meccsét a hét különböző napján játssza, vasárnap pedig mindenki számára pihenőnap lehessen; matematikailag leírva a 6-reguláris páratlan gráf () 6-élszínezését keresik. Ha 3, 4 vagy 8, az élszínezéséhez színre van szükség, de ha 5, 6 vagy 7, elegendő szín is.; ; .
Definíciók Ahogy az ellenpáros csúcsszínezésre is igaz, a gráf élszínezése alatt külön jelző nélkül is az élek „jó” színezése értendő, amikor a szomszédos – itt: ugyanabból a csúcsból kiinduló – élek mindig különböző színűek. A gráf egy élszínezése ekvivalensnek tekinthető az élgráf csúcsszínezésének (az élgráf csúcsai az eredeti gráf éleinek, élei pedig az eredeti gráf szomszédos élpárjainak felelnek meg).
Egy különböző színnel történő jó élszínezést (jó) -élszínezésnek neveznek. Az a gráf, amihez tartozik (jó) -élszínezés, -élszínezhető. Az a legkevesebb szín, amivel élszínezhető, a -hez tartozó élkromatikus szám vagy kromatikus index, . Az élkromatikus számot néha -vel is jelölik, az alsó indexben lévő egyessel arra utalva, hogy az élek egydimenziós objektumok. Egy gráf akkor -élkromatikus, ha kromatikus indexe éppen . Az élkromatikus szám nem tévesztendő össze a csúcsszínezéshez szükséges színeket számoló kromatikus számmal, melynek jele vagy .
Ha külön nem jelöljük, a cikkben szereplő gráfok mind egyszerűek, nem pedig multigráfok, melyekben többszörös élek, esetleg hurokélek is megengedettek. Az élszínezési problémákban az egyszerű gráfok viselkedése jelentősen eltér a multigráfokétól, így nem kevés odafigyelést igényel az élszínezési tételek kiterjesztése egyszerű gráfokról multigráfokra.
Párosítással való kapcsolata
Egy gráfhoz tartozó párosítás az adott gráfon belül közös csúccsal nem rendelkező élek halmaz; egy teljes párosítás olyan párosítás, mely a gráf összes csúcsát lefedi, egy maximális elemszámú párosítás pedig olyan párosítás, ami a gráf lehető legtöbb élét tartalmazza. Élszínezéskor az azonos színű élek egymással nem lehetnek szomszédosak, ezért párosítást alkotnak. Tehát a gráf egy jó élszínezése ugyanazt jelenti, mint a gráf diszjunkt párosításokba particionálását.
Ha adott gráf maximális elemszámú párosítása kis méretű, sok párosításra lesz szükség a gráf összes éleinek lefedéséhez. Ebből a gondolatmenetből formálisabban az következik, hogy ha egy gráf összesen éllel rendelkezik, melyek közül legfeljebb él tartozik egy maximális elemszámú párosításhoz, akkor a gráf minden élszínezésében legalább különböző színnek kell szerepelnie., p. 134. Például az ábrán látható 16 csúcsú síkgráfnak éle van. Ebben a gráfban nem lehet szó teljes párosításról; hiszen, ha a középső csúcsot párosítjuk, a megmaradó párosítatlan csúcsok három különböző összefüggő komponensbe különülnek el, melyek négy, öt, illetve öt csúcsból állnak, a páratlan csúcsból álló komponensek pedig nem párosíthatók teljesen. A gráf maximális elemszámú párosítása hét élt tartalmaz, tehát . Így a gráf élszínezéséhez legalább 24/7 szín szükséges, és mivel a színek száma csak egész szám lehet, legalább négy.
Ha egy fokszámú reguláris gráfban nincs teljes párosítás, az iménti alsó korlát segítségével belátható, hogy legalább színre lesz szükség. Ha specifikusan egy páratlan számú csúccsal rendelkező reguláris gráfot tekintünk (például a páratlan teljes gráfokat), az ilyen gráfokban a kézfogási lemma miatt -nak párosnak kell lennie. Azonban a egyenlőtlenség nem magyarázza meg teljesen a reguláris gráfok kromatikus indexét, vannak ugyanis olyan reguláris gráfok, melyekben van teljes párosítás, mégsem k-élszínezhetők. Például a Petersen-gráf reguláris, és éllel teljes párosításaiban, mégsem létezik 3-élszínezése.
Fokszámmal való kapcsolata
Vizing-tétel
A gráf élkromatikus száma szorosan kapcsolódik a maximális fokszámhoz, ami egyben megadja a bármely csúcsából kiinduló élek maximális számát. Az nyilvánvaló, hogy , hiszen ha különböző él ugyanabban a csúcsban találkozik, akkor ezekhez az éleknek mind különböző színeket kell rendelni, ami csak akkor lehetséges, ha legalább szín kiosztható. A Vizing-tétel állítása szerint ez a korlát csaknem éles: bármely gráf élkromatikus száma vagy , vagy . Ha , G az 1. osztályba tartozik (class 1); egyébként a 2. osztályba (class 2).
Minden páros gráf, és csaknem minden véletlen gráf is az 1. osztályba tartozik.. Annak eldöntése azonban, hogy tetszőleges gráf az 1. osztályba tartozik-e, NP-teljes nehézségű feladat..
bebizonyította, hogy a legalább nyolc maximális fokszámú síkbarajzolható gráfok az 1. osztályba tartoznak, és sejtése szerint ugyanez igaz azokra, melyek maximális fokszáma hat vagy hét. Másrészről léteznek olyan síkbarajzolható gráfok, melyek maximális fokszáma kettő és öt közötti, és a 2. osztályba esnek. A sejtést azóta bebizonyították a hét maximális fokszámú gráfokra.. Az hídmentes síkbarajzolható 3-reguláris gráfok mind az 1. osztályba tartoznak; ez a négyszíntétellel ekvivalens állítás.; .
Reguláris gráfok Egy k-reguláris gráf 1-faktorizációja a gráf éleit teljes párosításokba particionálja, ami megegyezik a gráf k-élszínezésével. Más szóval, egy reguláris gráfnak pontosan akkor létezik 1-faktorizációja, ha az 1. osztályba tartozik. Ennek speciális eseteként a 3-reguláris gráfok 3-élszínezését néha Tait-színezésnek is hívják.
Nem minden reguláris gráf 1-faktorizálható; például a Petersen-gráf sem. Általánosabban a snarkokat úgy definiálják, mint a gráfok, melyek a Petersen-gráfhoz hasonlóan hídmentesek, 3-regulárisok és a 2. osztályba tartoznak.
tétele szerint minden páros reguláris gráfnak van 1-faktorizációja. A tételt korábban a projektív konfigurációk kontextusában Ernst Steinitz fogalmazta meg és bizonyította.
Multigráfok
A multigráfokra, melyekben két csúcsot több, párhuzamos él is összeköthet, szintén léteznek a Vizing-tételhez hasonló, de annál gyengébb eredmények, melyek az élkromatikus számot, a maximális fokszámot és a multiplicitást (a párhuzamos élcsomagokban lévő maximális élszámot) hozzák összefüggésbe. Az, hogy a Vizing-tétel nem általánosítható egyszerűen multigráfokra, egyszerűen belátható, ha egy Shannon-multigráfot tekintünk. Ez egy három csúcsból és három élkötegből álló multigráf, melynek három csúcsát páronként párhuzamos él köti össze. Az ábrán látható példában (az egyes csúcsok a háromból csak két élköteghez csatlakoznak), de az élkromatikus szám (összesen él van a multigráfban, és bármely két él szomszédos, ezért az összes élnek különböző színűnek kell lennie). Egy Vizinget is megihlető eredményében, p. 136. megmutatta, hogy az ábrán a legrosszabb eset látható: bármely multigráfra. Ezen felül bármely multigráfra igaz a egyenlőtlenség, ami egyszerű gráfok esetén (melyekre ) a Vizing-tételre redukálódik.
Algoritmusok Mivel annak tesztelése, hogy egy gráf az 1. osztályba tartozik-e, NP-teljes, ezért nem ismert olyan polinom idejű algoritmus, ami minden gráfot optimálisan élszínezne. Léteznek azonban algoritmusok, melyek egyes kritériumok lazításával hatékonyan tudnak működni: csak bizonyos gráfosztályokon működnek, nem minden esetben használnak optimális számú színt vagy nem minden esetben futnak le polinom idő alatt.
Egyes gráfosztályok optimális színezése Páros gráfok, illetve maximális fokszámú multigráfok esetén a színek optimális száma éppen . megmutatta, hogy ezeknek a gráfoknak az optimális színezése , azaz csaknem lineáris időben megtalálható, ahol a gráf éleinek száma; egyszerűbb, de valamivel lassabb algoritmusokat ír le és . algoritmusa indulásakor a bemeneti gráfot regulárissá alakítja anélkül, hogy fokszámát növelné vagy jelentősen megnövelné a méretét: a párosítás ugyanazon részébe tartozó egyes csúcspárokat összevon, néhány csúcsot és élt hozzáad a gráfhoz. Ezután ha a fokszám páratlan, Alon közel lineáris időben keres egy teljes párosítást, hozzárendel egy színt, majd eltávolítja a gráfból, ami után a fokszám párossá válik. Végül Alon alkalmazza megfigyelését, miszerint a gráf Euler-útjának éleit váltakozva kiválasztva a gráfot két reguláris részgráffá lehet particionálni, ezzel az élszínezési problémát két kisebb részproblémára felosztva; algoritmusa ezután a két részproblémát rekurzív módon oldja meg. Az algoritmus teljes időigénye .
A maximális fokszámú síkbarajzolható gráfok esetén a színek optimális száma pontosan . Ha az erősebb feltétel is teljesül, miszerint , az optimális élszínezés lineáris időben megtalálható .
Az optimálisnál több színt használó algoritmusok A és által leírt polinom idejű algoritmusok; lásd Misra & Gries élszínezési algoritmusa.