Élszínezés

A Desargues-gráf 3-élszínezése.

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 különböző színnel, adott k-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 Δ+1. 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 3Δ/2 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 Δ+1-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.^[1]

A K₈ teljes gráf 7-élszínezésének mértani konstrukciója. A hét színosztály mindegyikéhez tartozik egy-egy él a középpontból a sokszög egy csúcsához, és három, az elsőre merőleges él.

Egy K_n teljes gráf n − 1-élszínezhető, amennyiben n páros; ez a Baranyai-tétel speciális esete. (Soifer 2008) a következő geometriai konstrukciót adja a színezésre: helyezzünk el n pontot egy (n − 1)-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 n páratlan, n színre van szükség: az egyes színek csak (n − 1)/2 élhez tartozhatnak, az összes él 1/n részéhez.^[2]

Több szerző tanulmányozta a páratlan gráfok élszínezéseit. A páratlan gráfok olyan n-reguláris gráfok, melyeknek csúcsai 2n − 1 méretű játékoshalmazból kiválasztott n − 1 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 n = 3 esetnek a jól ismert Petersen-gráf felel meg. (Biggs 1972) az n = 6 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 (O₆) 6-élszínezését keresik. Ha n 3, 4 vagy 8, az O_n élszínezéséhez n + 1 színre van szükség, de ha 5, 6 vagy 7, elegendő n szín is.^[3]

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 G gráf egy élszínezése ekvivalensnek tekinthető az L(G) é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 különböző színnel történő jó élszínezést (jó) k-élszínezésnek neveznek. Az a gráf, amihez tartozik (jó) k-élszínezés, k-élszínezhető. Az a legkevesebb szín, amivel G élszínezhető, a G-hez tartozó élkromatikus szám vagy kromatikus index, χ′(G). Az élkromatikus számot néha χ₁(G)-vel is jelölik, az alsó indexben lévő egyessel arra utalva, hogy az élek egydimenziós objektumok. Egy gráf akkor k-élkromatikus, ha kromatikus indexe éppen k. 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 χ(G) vagy χ₀(G).

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

Ennek a 3-reguláris síkbarajzolható gráfnak 16 csúcsa és 24 éle van, de a maximális elemszámú párosításai csak 7 élt tartalmaznak. Ezért élszínezéséhez négy színre van szükség.

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 m é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 m/β különböző színnek kell szerepelnie.^[4] Például az ábrán látható 16 csúcsú síkgráfnak m = 24 é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 β = 7. Í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 k 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 k + 1 színre lesz szükség.^[4] 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 k-nak párosnak kell lennie. Azonban a χ′ ≥ m/β 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, m = 15 és β = 5 éllel teljes párosításaiban, mégsem létezik 3-élszínezése.

Fokszámmal való kapcsolata

Vizing-tétel

Bővebben: Vizing-tétel

A G gráf élkromatikus száma szorosan kapcsolódik a Δ(G) maximális fokszámhoz, ami egyben megadja a G bármely csúcsából kiinduló élek maximális számát. Az nyilvánvaló, hogy χ′(G) ≥ Δ(G), hiszen ha Δ különböző él ugyanabban a v 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 Δ(G), vagy Δ(G) + 1. Ha χ′(G) = Δ(G), G az 1. osztályba tartozik (class 1); egyébként a 2. osztályba (class 2).

Minden páros gráf,^[5] és csaknem minden véletlen gráf is az 1. osztályba tartozik.^[6] Annak eldöntése azonban, hogy tetszőleges gráf az 1. osztályba tartozik-e, NP-teljes nehézségű feladat.^[7]

(Vizing 1965) 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.^[8] 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.^[9]

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.

(Kőnig 1916) 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

Egy Shannon-multigráf, hatos fokszámmal és hármas él-multiplicitással, aminek élszínezéséhez legalább kilenc színre van szükség

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 χ′(G) élkromatikus számot, a Δ(G) maximális fokszámot és a μ(G) 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 μ(G) párhuzamos él köti össze. Az ábrán látható példában Δ(G) = 2μ(G) (az egyes csúcsok a háromból csak két élköteghez csatlakoznak), de az élkromatikus szám 3μ(G) (összesen 3μ(G) é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^[10] (Shannon 1949) megmutatta, hogy az ábrán a legrosszabb eset látható: χ′(G) ≤ (3/2)Δ(G) bármely G multigráfra. Ezen felül bármely G multigráfra igaz a χ′(G) ≤ Δ(G) + μ(G) egyenlőtlenség, ami egyszerű gráfok esetén (melyekre μ(G) = 1) 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 Δ. (Cole, Ost & Schirra 2001) megmutatta, hogy ezeknek a gráfoknak az optimális színezése O(m log Δ), azaz csaknem lineáris időben megtalálható, ahol m a gráf éleinek száma; egyszerűbb, de valamivel lassabb algoritmusokat ír le (Cole & Hopcroft 1982) és (Alon 2003). (Alon 2003) 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 (Gabow 1976) 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 O(m log m).

A Δ ≥ 7 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 Δ ≥ 9, az optimális élszínezés lineáris időben megtalálható (Cole & Kowalik 2008).

Az optimálisnál több színt használó algoritmusok

A (Misra & Gries 1992) és (Gabow et al. 1985) által leírt polinom idejű algoritmusok; lásd Misra & Gries élszínezési algoritmusa.

Multigráfok esetén (Karloff & Shmoys 1987) a következő, Eli Upfalnak tulajdonított algoritmust írja el. Alakítsuk át a bemeneti G multigráfot: a páratlan fokszámú csúcsokhoz adjunk egy vele éllel összekötött csúcsot, így lesz a gráfban Euler-séta; ezután keressünk egy Euler-sétát és válasszunk számára egy orientációt. Alakítsunk ki egy H páros gráfot, melyben G minden csúcsának két kópiája szerepel, a bipartíció mindkét oldalán egy-egy, és bipartíció bal oldalán található u csúcstól akkor vezet él a jobb oldalán található v csúcshoz, ha G orientált Euler-sétájában szerepel u-ból v-be vezető él. Alkalmazzunk egy páros gráf-élszínező algoritmust H-ra. H minden színosztálya G olyan élhalmazának felel meg, ami egy kettő maximális fokszámú részgráfot alkot; tehát utak és körök diszjunkt unióját, így H minden színosztályához lehetséges három G-beli színosztályt alkotni. Ezen algoritmus időigénye a páros gráf élszínezési idejéhez kötött, ami (Cole, Ost & Schirra 2001) algoritmusát használva O(m log Δ). A felhasznált színek száma legfeljebb ${\displaystyle 3\left\lceil {\frac {\Delta }{2}}\right\rceil }$, ami közel van, ha nem is éri el a ${\displaystyle \left\lfloor {\frac {3\Delta }{2}}\right\rfloor }$ Shannon-korlátot. Viszonylag egyszerűen párhuzamos algoritmussá is alakítható. Ugyanebben a cikkben Karloff és Shmoys bemutatnak egy lineáris idejű algoritmust, ami három maximális fokszámú multigráfokat négy színnel élszínez (ami Shannon és Vizing korlátainak is megfelel). Ez az algoritmus hasonló elven működik: új csúcs hozzáadásával biztosítja az Euler-séta létezését, megkeresi a sétát, majd a séta váltakozó éleinek kiválasztásával a gráfot két részgráfra bontja, melyek maximális fokszáma kettő. Ezeknek a részgráfoknak az útjai és páros körei két-két színnel színezhetők. A lépést követően minden megmaradó páratlan kör tartalmaz legalább egy olyan élt, aminek színezéséhez az ellentétes részgráf valamelyik színét lehet választani. A páratlan színből ezt ez élt eltávolítva egy út marad, ami a saját részgráf két színével élszínezhető.

Egy olyan mohó színezési algoritmus, ami egyenként vizsgálja a gráf vagy multigráf éleit, és minden élhez az első elérhető színt társítja, néha akár 2Δ − 1 színt is felhasználhat, ami csaknem kétszerese az optimális élszínezéshez szükségesnek. Előnye viszont, hogy online algoritmusban is alkalmazható, amikor a bemeneti gráf nem ismert előre; ebben a kontextusban versenyképességi hányadosa kettő, ami optimális: egyetlen online algoritmus sem érhet el ennél jobb teljesítményt.^[11] Ha azonban az élek véletlenszerűen érkeznek és a bemeneti gráf fokszáma legalább logaritmikus, akkor kisebb versenyképességi hányadosok is elérhetők.^[12]

Több szerző állított fel sejtést arra nézve, hogy tetszőleges multigráf frakcionális élkromatikus száma (egy olyan szám, ami lineáris programozás segítségével polinom időben számítható) legfeljebb eggyel tér el az élkromatikus számtól.^[13] Ha ezek a sejtések igaznak bizonyulnak, legfeljebb egy eltéréssel kiszámítható lenne a multigráfok élkromatikus száma, ami az egyszerű gráfok esetében a Vizing-tételnek felel meg. Általános esetben ezek a sejtéseket nem sikerült bizonyítani vagy cáfolni, biztosan igazak viszont abban az esetben, ha az élkromatikus szám legalább ${\displaystyle \Delta +{\sqrt {\Delta /2}}}$, ami az elegendően nagy multiplicitású multigráfoknál előfordul.^[14]

Egzakt algoritmusok

Könnyen tesztelhető, hogy egy gráf élszínezhető-e egy vagy két színnel, így az élszínezés első nem triviális esete annak vizsgálata, hogy adott gráf 3-élszínezhető-e. Ahogy (Kowalik 2009) megmutatta, egy gráf 3-élszínezhetőségének tesztelése O(1,344ⁿ) időben és polinom tárban elvégezhető. Bár ez az idő exponenciális, még így is lényegesen gyorsabb az összes lehetséges szín-él-hozzárendelés brute force-keresésénél. Minden n csúcsú, kétszeresen összefüggő 3-reguláris gráfnak O(2^n/2) 3-élszínezése van, melyek O(2^n/2) időben listázhatók (valamivel lassabban egyetlen színezés megkeresésénél); Greg Kuperberg megfigyelése szerint egy n/2-oldalú sokszög alapú hasáb gráfjának Ω(2^n/2) színezése van (az O jelölés szerint itt alsó, nem pedig felső korlátról van szó), amiből következik, hogy ez a korlát éles.^[15]

A bemeneti gráf élgráfjára egzakt csúcsszínezési algoritmusokat alkalmazva bármely m élű gráf optimális élszínezése lehetséges, a szükséges színek számától függetlenül, 2^mm^O(1) időben és exponenciális tárban, vagy O(2,2461^m) időben és csak polinom tárban (Björklund, Husfeldt & Koivisto 2009).

Mivel az élszínezés már három szín esetén is NP-teljes, valószínűtlen, hogy a színek száma szerint paraméterezve rögzített paraméter mellett kezelhető lenne. Kezelhető azonban más paramétereket választva. (Zhou, Nakano & Nishizeki 1996) megmutatta, hogy w favastagságnál az optimális élszínezés O(nw(6w)^{w(w + 1)/2}) időben kiszámítható, ami w-től ugyan szuperexponenciálisan függ, de a gráf csúcsainak n számának csak lineáris függvénye.

(Nemhauser & Park 1991) az élszínezési problémát egészértékű programozási eszközökkel definiálta és leírta tapasztalatait, amit egészértékű megoldóprogrammal szerzett gráfok élszínezésében. Nem végzett azonban bonyolultsági vizsgálatot a felhasznált algoritmusokon.

További tulajdonságok

Az egyedi 3-színezéssel rendelkező G(9,2) általánosított Petersen-gráf. A három színosztály egyikét a világos élek jelölik, a másik kettő megkapható vagy a világos élek 40°-os pozitív, illetve negatív irányú elforgatásával, vagy a sötét Hamilton-kör alternáló élekre particionálásával.

Egy gráf egyedi k-élszínezéssel rendelkezik ha pontosan egyféleképpen lehet az éleit k színosztályba particionálni, nem tekintve a színek k! lehetséges permutációját (permutáció erejéig). A k ≠ 3 esetben egyedi k-élszínezéssel kizárólag utak, körök és csillagok rendelkeznek, de a k = 3 esetben néhány további gráf is egyedileg k-élszínezhető. Minden egyedi 3-élszínezhető gráfnak pontosan három Hamilton-köre van (melyek a három színosztály valamelyikének törlésével állnak elő), de léteznek 3-reguláris gráfok három Hamilton-körrel, melyek nem egyedileg 3-élszínezhetők: ilyenek például a G(6n + 3, 2) általánosított Petersen-gráfok bármely n ≥ 2-re. Az egyetlen ismert nem síkbarajzolható egyedi 3-élszínezhető gráf a G(9,2) általánosított Petersen-gráf, és egy sejtés szerint nincs is több ilyen.^[16]

A K_3,3 teljes páros gráf, két színosztálya különálló, párhuzamos egyenes szakaszokként lerajzolva.

(Folkman & Fulkerson 1969) az olyan, nem növekvő m₁, m₂, m₃, ... számsorozatokat vizsgálta, melyekre igaz, hogy létezik G gráf jó élszínezése melyben m₁ él tartozik az első színhez, m₂ él a másodikhoz stb. Megfigyelték, hogy ha egy P sorozat „megvalósítható” ebben az értelemben, és lexikografikus sorrend szerint nagyobb mint az ugyanolyan összegű Q sorozat, akkor Q is megvalósítható. Hiszen, ha P > Q a lexikografikus sorrendben, akkor P átvihető Q-ba olyan lépések sorozatával, melyek mindegyike eggyel csökkenti az m_i számok valamelyikét és eggyel növeli valamely későbbi m_j számot (ahol i < j). Élszínezés tekintetében egy P-t megvalósító színezésnél ezek a lépések megfelelnek az i és j színek megcserélésével egy Kempe-láncban, ami a két szín között váltakozó maximális út. Továbbá, bármely gráf rendelkezik egyenletes élszínezéssel, tehát olyan optimális élszínezéssel, melyben bármely két színosztályba tartozó élek száma legfeljebb eggyel tér el.

A De Bruijn–Erdős-tétel segítségével a véges gráfok számos, élszínezéssel kapcsolatos tulajdonsága átfordítható végtelen gráfokra. Például a fokszám és az élkromatikus szám közötti összefüggést tárgyaló Shannon- és Vizing-tételek egyszerűen általánosíthatók végtelen gráfokra.^[17]

(Richter 2011) vizsgálta adott 3-reguláris gráf olyan lerajzolásának problémáját, ahol a lerajzolás minden éle három különböző lejtésszög valamelyikét veheti fel, és semelyik két él sem helyezkedik el ugyanazon az egyenesen. Ha egy ilyen lerajzolás létezik, akkor az élek lejtésszögei nyilvánvalóan egy 3-élszínezés színeiként is szolgálhatnak. Például a K_3,3 három ház–három kút-gráf esetén egy szabályos hatszög élei és nagyátlói megfeleltethetők egy 3-élszínezésnek. Richter megmutatta, hogy 3-reguláris egyszerű páros gráfokat és adott Tait-színezést tekintve pontosan akkor létezik ilyen, az adott színezésnek megfelelő lerajzolása, ha a gráf 3-szorosan élösszefüggő. Nem páros gráfokra a feltétel kissé bonyolultabb: adott színezéshez akkor létezik lerajzolás, ha a gráf páros dupla fedése (bipartite double cover) 3-élösszefüggő, és bármelyik egyszínű élpár törlésével még mindig olyan részgráfhoz jutunk, ami nem páros. Ezek a feltételek polinom időben még mind könnyen tesztelhetők; az a probléma azonban, ahol a 4-élszínezett 4-reguláris gráfok négy lejtésszöggel való lerajzolását vizsgáljuk, teljes az existential theory of the reals(wd) nagyobb osztályára nézve, ami legalább olyan nehéz bonyolultsági osztály, mint az NP-teljesség.

Amellett, hogy a gráf maximális fokszámához és maximális elemszámú párosítási számához köthető, az élkromatikus szám szoros kapcsolatban áll a G gráf la(G) lineáris arboricitásával is, ami azon lineáris erdők (diszjunkt útgráfok uniója) minimális száma, melyekbe a gráf élei felbonthatók. Egy párosítás a lineáris erdők speciális fajtája, megfordítva pedig, bármely lineáris erdő 2-élszínezhető, ezért minden G-re igaz, hogy la(G) ≤ χ′(G) ≤ 2 la(G). Az Akijama Dzsinről elnevezett Akijama-sejtés állítása szerint ${\displaystyle \mathop {\mathrm {la} } (G)\leq \left\lceil {\frac {\Delta +1}{2}}\right\rceil }$, amiből következne az előbbinél erősebb állítás, hogy 2 la(G) − 2 ≤ χ′(G) ≤ 2 la(G). A három maximális fokszámú gráfokra la(G) mindig pontosan kettő, tehát ebben az esetben a χ′(G) ≤ 2 la(G) korlát megegyezik a Vizing-tétel korlátjával.^[18]

Az élszínezés egyéb fajtái

A K_4,4 teljes páros gráf egy három erdőbe történő particionálása, ami azt mutatja, hogy a gráf arboricitása három.

Egy gráf Thue-száma az ahhoz minimálisan szükséges színek száma, hogy a jó élszínezésen belül bármely páros hosszúságú út első és második fele különböző színsorozatból álljon.

Egy gráf arboricitása az a minimális számú szín, ami szükséges ahhoz, hogy az azonos színosztályba tartozó élek ne alkossanak köröket (ellentétben a megszokott élszínezési problémával, ahol azt várjuk el, hogy ne legyenek azonos színű szomszédos élpárok). Ami megegyezik a minimális számú erdővel, melybe a gráf élei particionálhatók.^[19] Az élkromatikus számtól eltérően a gráf arboricitása polinom időben kiszámítható.^[20]

A lista-élszínezés az a probléma, melyben a gráf minden éléhez egy színlista van hozzárendelve, és úgy kell jó élszínezést találni, hogy minden élnél csak a lista színeiből lehet válogatni. A G gráf lista-élkromatikus száma az a legkisebb k szám, melynél bárhogy vannak pontosan az éleken a listaszínek elosztva, ha minden élnek legalább k él szerepel a listájában, garantáltan lehetséges a jó élszínezés. A lista-élkromatikus szám ezért legalább akkora, mint az élkromatikus szám. A részleges latin négyzetek kiegészítéséről szóló Dinitz-sejtés gráfelméleti átfogalmazása szerint a ${\displaystyle K_{n,n}}$ teljes páros gráf lista-élkromatikus száma éppen élkromatikus számával, ${\displaystyle n}$-nel egyenlő. (Galvin 1995) általánosabb állítást bizonyít, miszerint bármely páros multigráf lista-élkromatikus száma megegyezik élkromatikus számával. Egy általánosabb lista-élszínezési sejtés szerint ugyanez nem csak páros gráfokra, hanem tetszőleges hurokmentes multigráfra igaz.

A csúcsszínezés gyakoribb változatainak jelentős részét élszínezésre is kiterjesztették. Például a teljes élszínezés a teljes színezés élszínezési változata; ez olyan jó élszínezést jelent, melyben minden színpárnak legalább egy szomszédos élpárnál jelentkeznie kell, és melyben a cél a színek számának maximalizálása.^[21] Az erős élszínezés az erős színezés élszínezési változata, melyben bármely két, különböző végpontokkal rendelkező élnek különböző színűnek kell lennie.^[22] Az erős élszínezés alkalmazási területei közé tartoznak a vezeték nélküli hálózatok csatornakiosztási sémái.^[23]

Az aciklikus (körmentes) élszínezés az aciklikus színezés élszínezési változata, melyben bármely két színosztály aciklikus részgráfot (tehát erdőt) alkot.^[24] A ${\displaystyle G}$ gráf ${\displaystyle a'(G)}$ aciklikus kromatikus száma, ami a ${\displaystyle G}$ jó aciklikus élszínezéséhez szükséges legkisebb számú szín. Sejtések szerint ${\displaystyle a'(G)\leq \Delta +2}$, ahol ${\displaystyle \Delta }$ ${\displaystyle G}$ maximális fokszáma.^[25] A legjobb igazolt korlát jelenleg ${\displaystyle a'(G)\leq \lceil 3,74(\Delta -1)\rceil }$.^[26] A probléma könnyebbé válik, amikor ${\displaystyle G}$ girthparamétere magas. Specifikusan, létezik olyan ${\displaystyle c}$ konstans, melynél ha ${\displaystyle G}$ girthe legalább ${\displaystyle c\Delta \log \Delta }$, akkor ${\displaystyle a'(G)\leq \Delta +2}$.^[27] Egy hasonló eredmény szerint minden ${\displaystyle \epsilon >0}$-hoz tartozik egy olyan ${\displaystyle g}$ szám, melyre ha ${\displaystyle G}$ girthparamétere legalább ${\displaystyle g}$, akkor ${\displaystyle a'(G)\leq (1+\epsilon )\Delta }$.^[28]

(Eppstein 2008) tanulmányozta a 3-reguláris gráfok olyan 3-élszínezéseit, melyekben semelyik két olyan bikromatikus (két színnel színezett) kör sem osztozik egynél több élen egymással. Megmutatta, hogy egy ilyen élszínezés létezése ekvivalens olyan, háromdimenziós egész rácsra történő lerajzolással, melyben az élek párhuzamosak a koordinátatengelyekkel és bármely tengelypárhuzamos egyenes legfeljebb két csúcsot tartalmaz. A megszokott 3-élszínezési problémához hasonlóan az ilyen xyz-lerajzolás megkeresése is NP-teljes feladat.

A totális színezés a csúcs- és élszínezést kombinálja, sem érintkező élek, sem valamely él végpontjai nem lehetnek azonos színűek. A Vizing-tétel és a Brooks-tétel kombinációjaként azt a sejtést állították fel, hogy bármely gráfnak van olyan totális színezése, melyben a színek száma legfeljebb a maximális fokszám plusz kettővel egyezik meg – χ″(G) ≤ Δ(G) + 2 – de ezt csak néhány gráfcsaládra sikerült bizonyítani, az általános esetre nem.

Ha egy felületbe ágyazott 3-reguláris gráfra 3-élszínezést alkalmazunk, duális gráfja a felület olyan háromszögelését adja, ami szintén élszínezett (de nem feltétlenül jó élszínezéssel) úgy, hogy a háromszögek pontosan 1-1 éle tartozik 1-1 színhez. Más színezések, illetve háromszögelés-orientációk, a színek a csúcsokon vagy a háromszögelés tartományain való elosztására való helyi megszorításokkal együtt, alkalmasak lehetnek több fajta geometriai objektum kódolására. Például a téglalap-felosztások (egy téglalap felosztása kisebb téglalapokra oly módon, hogy minden csúcsban három téglalap találkozzon) kombinatorikusan leírhatók egy „reguláris címkézéssel”, méghozzá a felosztással duális háromszögelés éleinek olyan 2-színezésével, ahol minden egyes csúcsból kiinduló élek négy folytonos részszekvenciát alkotnak, melyeken belül a színek megegyeznek. Ez a címkézés duálisa magának a téglalapfelosztásnak, melyben a függőleges élek az egyik színt, a vízszintesek a másik színt kapják. A színezett élek csúcsok körül való megjelenésének sorrendjére vonatkozó hasonló lokális megszorítások felhasználhatók síkbarajzolható gráfok, illetve háromdimenziós, tengelypárhuzamos oldalú testek egyenes vonalú rácsba ágyazásának kódolására is. Mindhárom fajta reguláris címkézésre igaz, hogy egy rögzített gráf reguláris címkézéseinek halmaza disztributív hálót alkot, ami felhasználható az ugyanarra a gráfra épülő geometriai struktúrák gyors listázására (például az azonos vázzal rendelkező összes tengelypárhuzamos poliéder listázására) vagy egyéb megszorításoknak megfelelő struktúrák megkeresésére.^[29]

Egy determinisztikus véges állapotú gép felfogható olyan irányított gráfként, melyben minden csúcs ki-foka d, élei pedig úgy vannak d-színezve, hogy két, azonos csúcsból kiinduló élnek mindig különböző színe van. Az útszínezési probléma az azonos ki-fokú irányított gráf élszínezésének problémája, melyben az eredmény automatának van szinkronizáló szava. (Trahtman 2009) megoldotta az útszínezési problémát azt bebizonyítva, hogy ilyen színezés mindig található, amennyiben a bemeneti gráf erősen összefüggő és aperiodikus.

A Ramsey-tétel a K_n teljes gráfok olyan k-élszínezéseivel foglalkozik, ami valamely adott s-re elkerüli az egyszínű K_s teljes részgráfokat. A tétel szerint létezik olyan R_k(s) szám, melyre ha n ≥ R(s), ilyen színezés nem létezik. Például R₂(3) = 6, tehát a K₆ 2-élszínezésekor mindig lesz egyszínű háromszög.

Ha egy élszínezett gráf útján nem ismétlődnek a színek, szivárványútnak nevezzük. Egy gráf akkor szivárványszínezett, ha bármely két csúcsa között létezik szivárványút.

Egy ${\displaystyle G}$ gráf 1…t színekkel való élszínezése (élcímkézése) akkor intervallum-t-színezés, ha mind a t szín felhasználásra kerül és ${\displaystyle G}$ minden csúcsából kiinduló élek színei különbözőek és egész intervallumot alkotnak.

Alkalmazások

A teljes gráfok élszínezései felhasználhatók körmérkőzések lehető legkevesebb körben történő lebonyolítási rendjének meghatározására; itt a gráfok csúcsai a körmérkőzés résztvevőinek, az élei az egyes mérkőzéseknek, a színek pedig a mérkőzések egyes köreinek feleltethetők meg.^[30] Hasonló színezési technikák olyan sportverseny-párosítások esetében is használhatók, ahol nem játszik minden résztvevő mindenkivel; például az NFL-ben az adott évben egymással játszó csapatpárosokat az előző év eredményei alapján határozzák meg, majd a párosítások gráfján egy élszínező algoritmus futtatásával rendelik hozzá a hétvégéket az egyes meccsekhez.^[31] Ennél az alkalmazási területnél a Vizing-tétel biztosítja, hogy a csapatok bármilyen párosítását választják (feltéve, hogy semelyik két csapatnak nem kell egymással kétszer játszania egy évadban), mindig lehetséges olyan lebonyolítást találni, hogy legfeljebb eggyel több hétvégére legyen szükség, mint ahány meccs van csapatonként.

Az open shop-ütemezés olyan gyártásütemezési probléma, melynek szereplői a legyártandó tárgyak halmaza, minden tárgyhoz tartozik a rajta (tetszőleges sorrendben) végzendő műveletek halmaza, és minden műveletet adott munkagépen lehet elvégezni, ami alatt más műveletek nem végezhetők ugyanazon a munkagépen. Ha minden művelet ugyanannyi időt vesz igénybe, a probléma felírható egy páros multigráf élszínezéseként, melyben a bipartíció egyik felének csúcsai a legyártandó munkadaraboknak, a másik felének csúcsai a munkagépeknek, az élek az elvégzendő feladatoknak, a színek pedig az egyes időszeleteknek feleltethetők meg. Mivel a páros élszínezés polinom időben elvégezhető, ugyanez igaz az open-shop ütemezés ezen korlátozott esetére.^[32]

(Gandham, Dawande & Prakash 2005) a szenzorhálózatok időosztásos többszörös hozzáférési (TDMA) kommunikációs protokolljainak kapcsolatütemezésének problémáját az élszínezés egy variánsaként tanulmányozták. Ebben a problémában a vezeték nélküli hálózati éleihez úgy kell időréseket választani, hogy a szomszédos hálózati csomópontok interferencia nélkül tudjanak egymással kommunikálni. Erős élszínezést választva (és minden színhez két időrést rendelve, az mindkét iránynak egyet-egyet) megoldható a probléma, de a szükségesnél több időrés felhasználásával. Ehelyett a hálózat irányítatlan éleinek megduplázásával alkotott irányított gráf olyan színezését keresik, melyben minden uv irányított él színe eltér mind a v-ből, mind a v szomszédaiból kiinduló élek színeitől. Erre olyan heurisztikát javasolnak, ami egy (Δ + 1)-élszínezési elosztott algoritmuson alapul kiegészítve egy utófeldolgozási fázissal, ami újraütemezi az éleket, amik interferálnának egymással.

Az optikai szál-alapú kommunikáció útszínezési problémájában színeket (fényfrekvenciákat) rendelnek az egymással kommunikálni kívánó csomópontpárokhoz, valamint minden párhoz egy-egy útvonalat az optikai szálon keresztül, azzal a megszorítással, hogy az ugyanazt az útvonalat használó két páros nem használhatja ugyanazt a frekvenciát. Az olyan útvonalak, amik ugyanazok a hálózati kapcsolón mennek át, de más optikai szál-szegmensen, lehetnek azonos színűek. Ha a kommunikációs hálózat csillag topológiájú, ahol egy központi switch köti össze önálló szálakkal az egyes hálózati csomópontokat, az útszínezési probléma pontosan megfeleltethető egy gráf vagy multigráf élszínezésének, melyben a kommunikáló csomópontok a gráf csúcsai, az egymással kommunikálni akaró csúcsokat élek köti össze és a felhasználható frekvenciák az élszínezési probléma színeit adják. Általánosabb, fa topológiájú kommunikációs hálózatok esetén az egyes switchek csillaghálózatainak lokális útszínezési megoldásait összefoltozva kapható meg a globális megoldás.^[33]

Egyéb problémák

(Jensen & Toft 1995) 23 élszínezéssel kapcsolatos eldöntetlen problémát sorol fel. Közülük néhány:

• (Goldberg 1973) sejtése szerint az élkromatikus szám és a frakcionális élkromatikus szám legfeljebb eggyel térnek el egymástól, ami lehetővé tenné az élkromatikus szám polinom időben való approximációját.
• Jakobsen és mások több sejtése az élszínezés szempontjából kritikus gráfok szerkezetéről szól, olyan 2. osztályba tartozó gráfokról, melyek bármely részgráfjának vagy alacsonyabb a maximális fokszáma, vagy az 1. osztályba tartozik. Jakobsen eredeti sejtése szerint az összes kritikus gráf páratlan számú csúccsal rendelkezik, de ezt megcáfolták. A témában további nyitott sejtések az eredeti gyengébb változatai, illetve a kritikus gráfok és multigráfok csúcsainak számára állítanak fel korlátokat.
• Vizing problémája, avagy a 2. osztályba tartozó síkbarajzolható gráfok lehetséges maximális fokszámainak klasszifikációja.
• A. J. W. Hilton overfull részgráf sejtése, aminek állítása szerint a legalább n/3 fokszámmal rendelkező gráfok vagy az 1. osztályba tartoznak, vagy van olyan részgráfjuk, ami az eredetivel megegyező Δ fokszámú és páratlan k csúcsa van, éleinek száma pedig nagyobb mint Δ(k − 1)/2; Herbert Grötzsch és Paul Seymour hasonló sejtése pedig magas fokszámú gráfok helyett síkbarajzolható gráfokkal foglalkozik.
• Chetwynd és Hilton egy (esetleg Gabriel Andrew Dirac korábbi munkáira visszavezethető) sejtése szerint a páros n csúccsal és legalább n/2 fokszámmal rendelkező reguláris gráfok az 1. osztályba tartoznak.
• Claude Berge és D. R. Fulkerson sejtése szerint a hídmentes 3-reguláris egyszerű gráfok éleinek duplázásával kapott 6-reguláris multigráfok 6-élszínezhetők.
• Fiorini és Wilson sejtése szerint a K_1,3 mancson kívül egyetlen háromszögmentes síkbarajzolható gráf sem egyedileg 3-élszínezhető.
• Egy 2012-es sejtés szerint ha G d-reguláris síkbarajzolható multigráf, akkor G pontosan akkor d-élszínezhető, ha G páratlanul d-élösszefüggő (ami azt jelenti, hogy bármely páratlan méretű csúcshalmazából kimenő élek számossága nem kisebb d-nél). A d=3 eset egybeesik a négyszínsejtéssel, aminek a sejtés az általánosítása. Maria Chudnovsky, Katherine Edwards és Paul Seymour bizonyították, hogy egy 8-reguláris síkbarajzolható multigráf élkromatikus száma 8.^[34]

Fordítás

• Ez a szócikk részben vagy egészben az Edge coloring című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

1. (Soifer 2008), problem 16.4, p. 133.
2. (Soifer 2008), problem 16.5, p. 133. Az, hogy vagy n, vagy (n − 1) színre van szükség, a Vizing-tétel következménye.
3. (Biggs 1972); (Meredith & Lloyd 1973); (Biggs 1979).
4. (Soifer 2008), p. 134.
5. (Kőnig 1916)
6. (Erdős & Wilson 1977).
7. (Holyer 1981).
8. (Sanders & Zhao 2001).
9. (Tait 1880); (Appel & Haken 1976).
10. (Soifer 2008), p. 136.
11. (Bar-Noy, Motwani & Naor 1992).
12. (Bahmani, Mehta & Motwani 2010).
13. (Goldberg 1973); (Andersen 1977); (Seymour 1979).
14. (Chen, Yu & Zang 2011).
15. (Eppstein 2008).
16. (Schwenk 1989).
17. (Bosák 1972).
18. (Akiyama, Exoo & Harary 1980); (Habib & Péroche 1982); (Horák & Niepel 1982).
19. (Nash-Williams 1964).
20. (Gabow & Westermann 1992).
21. Bosák & Nešetřil (1976).
22. (Fouquet & Jolivet 1983); (Mahdian 2002); (Frieze, Krivelevich & Sudakov 2005); (Cranston 2006).
23. Barrett et al. (2006).
24. (Alon, Sudakov & Zaks 2001); (Muthu, Narayanan & Subramanian 2007).
25. (Fiamčik 1978); (Alon, Sudakov & Zaks 2001)
26. Giotis et al. (2015).
27. Alon, Sudakov & Zaks (2001).
28. Cai et al. (2014).
29. (Eppstein 2010).
30. (Burke, De Werra & Kingston 2004).
31. (Skiena 2008).
32. (Williamson et al. 1997).
33. (Erlebach & Jansen 2001).
34. Chudnovsky, Edwards & Seymour (2012).

• Akiyama, Jin; Exoo, Geoffrey & Harary, Frank (1980), "Covering and packing in graphs. III. Cyclic and acyclic invariants", Mathematica Slovaca 30 (4): 405–417.
• Alon, Noga (2003), "A simple algorithm for edge-coloring bipartite multigraphs", Information Processing Letters 85 (6): 301–302, DOI 10.1016/S0020-0190(02)00446-5.
• Alon, Noga; Sudakov, Benny & Zaks, Ayal (2001), "Acyclic edge colorings of graphs", Journal of Graph Theory 37 (3): 157–167, DOI 10.1002/jgt.1010.
• Andersen, Lars Døvling (1977), "On edge-colourings of graphs", Mathematica Scandinavica 40 (2): 161–175. As cited by (Chen, Yu & Zang 2011).
• Appel, K. & Haken, W. (1976), "Every planar map is four colorable", Bulletin of the American Mathematical Society 82 (5): 711–712, DOI 10.1090/S0002-9904-1976-14122-5.
• Bahmani, Bahman; Mehta, Aranyak & Motwani, Rajeev (2010), "A 1.43-competitive online graph edge coloring algorithm in the random order arrival model", Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '10), pp. 31–39, <http://portal.acm.org/citation.cfm?id=1873601.1873605>.
• Bar-Noy, Amotz; Motwani, Rajeev & Naor, Joseph (1992), "The greedy algorithm is optimal for on-line edge coloring", Information Processing Letters 44 (5): 251–253, DOI 10.1016/0020-0190(92)90209-E.
• Barrett, C.L.; Istrate, G. & Kumar, V.S.A. et al. (2006), "Strong edge coloring for channel assignment in wireless radio networks", Proc. Fourth Annual IEEE International Conference on Pervasive Computing and Communications Workshops (PerCom Workshops 2006), pp. 106, ISBN 0-7695-2520-2, DOI 10.1109/PERCOMW.2006.129.
• Biggs, Norman (1972), Guy, Richard K., ed., "An edge-colouring problem", American Mathematical Monthly 79 (9): 1018–1020, DOI 10.2307/2318076.
• Biggs, Norman (1979), "Some odd graph theory", Second International Conference on Combinatorial Mathematics, vol. 319, Annals of the New York Academy of Sciences, pp. 71–81, DOI 10.1111/j.1749-6632.1979.tb32775.x.
• Björklund, Andreas; Husfeldt, Thore & Koivisto, Mikko (2009), "Set partitioning via inclusion-exclusion", SIAM Journal on Computing 39 (2): 546–563, DOI 10.1137/070683933.
• Bosák, Juraj (1972), "Chromatic index of finite and infinite graphs", Czechoslovak Mathematical Journal 22 (97): 272–290.
• Bosák, Juraj & Nešetřil, Jaroslav (1976), "Complete and pseudocomplete colourings of a graph", Matematicky Časopis Slovenskej Akadémie Vied 26 (3): 171–184.
• Cai, X. S.; Perarnau, G. & Reed, B. A. et al. (2014), Acyclic edge colourings of graphs with large girth.
• Burke, E.; De Werra, D. & Kingston, J. (2004), "5.6.5 Sports Timetabling", in J. L., Gross & Yellen, J., Handbook of Graph Theory, CRC Press, p. 462, ISBN 978-1-58488-090-5.
• Chen, Guantao; Yu, Xingxing & Zang, Wenan (2011), "Approximating the chromatic index of multigraphs", Journal of Combinatorial Optimization 21 (2): 219–246, DOI 10.1007/s10878-009-9232-y.
• Chudnovsky, Maria; Edwards, Katherine & Seymour, Paul (2012), Edge-colouring eight-regular planar graphs.
• Cole, Richard & Hopcroft, John (1982), "On edge coloring bipartite graphs", SIAM Journal on Computing 11 (3): 540–546, DOI 10.1137/0211043.
• Cole, Richard & Kowalik, Łukasz (2008), "New linear-time algorithms for edge-coloring planar graphs", Algorithmica 50 (3): 351–368, DOI 10.1007/s00453-007-9044-3.
• Cole, Richard; Ost, Kirstin & Schirra, Stefan (2001), "Edge-coloring bipartite multigraphs in O(E log D) time", Combinatorica 21 (1): 5–12, DOI 10.1007/s004930170002.
• Cranston, Daniel W. (2006), "Strong edge-coloring of graphs with maximum degree 4 using 22 colors", Discrete Mathematics 306 (21): 2772–2778, DOI 10.1016/j.disc.2006.03.053.
• Eppstein, David (2008), "The topology of bendless three-dimensional orthogonal graph drawing", in Tollis, Ioannis G. & Patrignani, Marizio, Proc. 16th Int. Symp. Graph Drawing, vol. 5417, Lecture Notes in Computer Science, Heraklion, Crete: Springer-Verlag, pp. 78–89.
• Eppstein, David (2010), "Regular labelings and geometric structures", Proc. 22nd Canadian Conference on Computational Geometry (CCCG 2010), University of Manitoba, <http://www.cs.umanitoba.ca/~cccg2010/electronicProceedings/invitedpaper2.pdf> Archiválva 2012. március 20-i dátummal a Wayback Machine-ben.
• Erdős, Paul & Wilson, Robin J. (1977), "Note on the chromatic index of almost all graphs", Journal of Combinatorial Theory, Series B 23 (2–3): 255–257, doi:10.1016/0095-8956(77)90039-9, <http://www.renyi.hu/~p_erdos/1977-20.pdf>.
• Erlebach, Thomas & Jansen, Klaus (2001), "The complexity of path coloring and call scheduling", Theoretical Computer Science 255 (1–2): 33–50, DOI 10.1016/S0304-3975(99)00152-8.
• Fiamčik, J. (1978), "The acyclic chromatic class of a graph", Math. Slovaca 28: 139–145.
• Fiorini, S. & Wilson, Robin James (1977), Edge-colourings of graphs, vol. 16, Research Notes in Mathematics, London: Pitman, ISBN 0-273-01129-4.
• Folkman, Jon & Fulkerson, D. R. (1969), "Edge colorings in bipartite graphs", Combinatorial Mathematics and its Applications (Proc. Conf., Univ. North Carolina, Chapel Hill, N.C., 1967), Chapel Hill, N.C.: Univ. North Carolina Press, pp. 561–577.
• Fouquet, J.-L. & Jolivet, J.-L. (1983), "Strong edge-colorings of graphs and applications to multi-k-gons", Ars Combinatoria 16 (A): 141–150.
• Frieze, Alan M.; Krivelevich, Michael & Sudakov, Benny (2005), "The strong chromatic index of random graphs", SIAM Journal on Discrete Mathematics 19 (3): 719–727 (electronic), DOI 10.1137/S0895480104445757.
• Gabow, Harold N. (1976), "Using Euler partitions to edge color bipartite multigraphs", International Journal of Computer and Information Sciences 5 (4): 345–355, DOI 10.1007/BF00998632.
• Gabow, Harold N.; Nishizeki, Takao & Kariv, Oded et al. (1985), Algorithms for edge-coloring graphs, Tech. Report TRECIS-8501, Tohoku University.
• Gabow, Harold N. & Westermann, Herbert H. (1992), "Forests, frames, and games: algorithms for matroid sums and applications", Algorithmica 7 (5–6): 465–497, DOI 10.1007/BF01758774.
• Galvin, F. (1995), "The list chromatic index of a bipartite multigraph", Journal of Combinatorial Theory, Series B 63 (1): 153–158, DOI 10.1006/jctb.1995.1011.
• Gandham, S.; Dawande, M. & Prakash, R. (2005), "Link scheduling in sensor networks: distributed edge coloring revisited", Proc. 24th INFOCOM, vol. 4, pp. 2492–2501, ISBN 0-7803-8968-9, DOI 10.1109/INFCOM.2005.1498534.
• Giotis, I.; Kirousis, L. & Psaromiligkos, K. I. et al. (2015), "On the algorithmic Lovász Local Lemma and acyclic edge coloring", Proceedings of the Twelfth Workshop on Analytic Algorithmics and Combinatorics (ANALCO), p. 16, ISBN 978-1-61197-376-1, DOI 10.1137/1.9781611973761.2.
• Goldberg, M. K. (1973), "Multigraphs with a chromatic index that is nearly maximal", Diskret. Analiz. (no. 23): 3–7, 72. As cited by (Chen, Yu & Zang 2011).
• Habib, M. & Péroche, B. (1982), "Some problems about linear arboricity", Discrete Mathematics 41 (2): 219–220, DOI 10.1016/0012-365X(82)90209-6.
• Holyer, Ian (1981), "The NP-completeness of edge-coloring", SIAM Journal on Computing 10 (4): 718–720, DOI 10.1137/0210055.
• Horák, Peter & Niepel, Ľudovít (1982), "A short proof of a linear arboricity theorem for cubic graphs", Acta Mathematica Universitatis Comenianae 40/41: 275–277.
• Jensen, Tommy R. & Toft, Bjarne (1995), Graph Coloring Problems, New York: Wiley-Interscience, ISBN 0-471-02865-7.
• Karloff, Howard J. & Shmoys, David B. (1987), "Efficient parallel algorithms for edge coloring problems", Journal of Algorithms 8 (1): 39–52, DOI 10.1016/0196-6774(87)90026-5.
• Kőnig, D. (1916), "Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre", Mathematische Annalen 77 (4): 453–465, doi:10.1007/BF01456961, <http://gdz.sub.uni-goettingen.de/index.php?id=11&PPN=PPN235181684_0077&DMDID=DMDLOG_0051&L=1>. Hozzáférés ideje: 2018-03-29 Archiválva 2015. január 19-i dátummal a Wayback Machine-ben.
• Kowalik, Łukasz (2009), "Improved edge-coloring with three colors", Theoretical Computer Science 410 (38–40): 3733–3742, DOI 10.1016/j.tcs.2009.05.005.
• Mahdian, Mohammad (2002), "On the computational complexity of strong edge coloring", Discrete Applied Mathematics 118 (3): 239–248, DOI 10.1016/S0166-218X(01)00237-2.
• Meredith, Guy H. J. & Lloyd, E. Keith (1973), "The footballers of Croam", Journal of Combinatorial Theory, Series B 15 (2): 161–166, DOI 10.1016/0095-8956(73)90016-6.
• Misra, J. & Gries, David (1992), "A constructive proof of Vizing's Theorem", Information Processing Letters 41 (3): 131–133, DOI 10.1016/0020-0190(92)90041-S.
• Muthu, Rahul; Narayanan, N. & Subramanian, C. R. (2007), "Improved bounds on acyclic edge colouring", Discrete Mathematics 307 (23): 3063–3069, DOI 10.1016/j.disc.2007.03.006.
• Nash-Williams, C. St. J. A. (1964), "Decomposition of finite graphs into forests", Journal of the London Mathematical Society, Second Series 39: 12, DOI 10.1112/jlms/s1-39.1.12
• Nemhauser, George L. & Park, Sungsoo (1991), "A polyhedral approach to edge coloring", Operations Research Letters 10 (6): 315–322, DOI 10.1016/0167-6377(91)90003-8.
• Richter, David A. (2011), "How to draw a Tait-colorable graph", in Brandes, Ulrik & Cornelsen, Sabine, Proc. 18th International Symposium on Graph Drawing (GD 2010), vol. 6502, Lecture Notes in Computer Science, Springer-Verlag, pp. 353–364, ISBN 978-3-642-18468-0, DOI 10.1007/978-3-642-18469-7_32.
• Sanders, Daniel P. & Zhao, Yue (2001), "Planar graphs of maximum degree seven are class I", Journal of Combinatorial Theory, Series B 83 (2): 201–212, DOI 10.1006/jctb.2001.2047.
• Seymour, P. D. (1979), "On multicolourings of cubic graphs, and conjectures of Fulkerson and Tutte", Proceedings of the London Mathematical Society, Third Series 38 (3): 423–460, DOI 10.1112/plms/s3-38.3.423.
• Schwenk, Allen J. (1989), "Enumeration of Hamiltonian cycles in certain generalized Petersen graphs", Journal of Combinatorial Theory, Series B 47 (1): 53–59, DOI 10.1016/0095-8956(89)90064-6.
• Shannon, Claude E. (1949), "A theorem on coloring the lines of a network", J. Math. Physics 28: 148–151.
• Skiena, Steven S. (2008), "16.8 Edge Coloring", The Algorithm Design Manual (2nd ed.), Springer-Verlag, pp. 548–550, ISBN 978-1-84800-069-8, DOI 10.1007/978-1-84800-070-4_16. See also web site for this section of the book in the Stony Brook Algorithm Repository.
• Soifer, Alexander (2008), The Mathematical Coloring Book, Springer-Verlag, ISBN 978-0-387-74640-1.
• Tait, P. G. (1880), "Remarks on the colourings of maps", Proc. R. Soc. Edinburgh 10: 729.
• Trahtman, Avraham N. (2009), "The road coloring problem", Israel Journal of Mathematics 172 (1): 51–60, DOI 10.1007/s11856-009-0062-5.
• Vizing, V. G. (1964), "On an estimate of the chromatic class of a p-graph", Diskret. Analiz. 3: 25–30.
• Vizing, V. G. (1965), "Critical graphs with given chromatic class", Metody Diskret. Analiz. 5: 9–17. (In Russian.)
• Williamson, D. P.; Hall, L. A. & Hoogeveen, J. A. et al. (1997), "Short shop schedules", Operations Research 45 (2): 288–294, DOI 10.1287/opre.45.2.288.
• Zhou, Xiao; Nakano, Shin-ichi & Nishizeki, Takao (1996), "Edge-coloring partial k-trees", Journal of Algorithms 21 (3): 598–617, DOI 10.1006/jagm.1996.0061.