Zbarvení okrajů

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 28. září 2022; ověření vyžaduje 1 úpravu .

Barvení hran je přiřazení „barev“ hranám grafu takovým způsobem, že žádné dvě sousední hrany nemají stejnou barvu. Barvení hran je jedním z různých typů vybarvování grafů. Problém zbarvení hran se ptá, zda je možné obarvit okraje daného grafu maximálně různými barvami pro danou hodnotu nebo pro minimální možný počet barev. Minimální počet barev potřebný k obarvení hran daného grafu se nazývá chromatický index grafu. Například okraje grafu na obrázku mohou být obarveny třemi barvami, ale nemohou být obarveny dvěma, takže graf má chromatický index 3. $k$ $k$

Podle Vizingova teorému je počet barev potřebný pro obarvení hran jednoduchého grafu buď roven maximálnímu stupni vrcholů nebo . U některých grafů, jako jsou bipartitní grafy a rovinné grafy vysokého stupně , je počet barev vždy , zatímco u multigrafů může být počet barev až . Existují polynomiální časové algoritmy, které produkují optimální obarvení bipartitních grafů a obarvení jednoduchého nebipartitního grafu počtem barev . V obecném případě je však problém najít optimální zbarvení čáry NP-úplný a nejrychlejší známý algoritmus pro něj běží v exponenciálním čase. Bylo studováno mnoho variant problému zbarvení hran, ve kterých podmínky pro přiřazení barvy k hraně musí splňovat jiné podmínky než konjugace. Problémy s barvením hran mají uplatnění v problémech plánování a přiřazování frekvencí v sítích s optickými vlákny . $\Delta$ $\Delta +1$ $\Delta$ $3{\Delta }/2$ ${\Delta }+1$

Příklady

Cyklus grafu lze vybarvit 2 barvami, pokud je délka cyklu sudá - stačí použít 2 barvy postupně, postupně procházet okraje cyklu. V případě liché délky jsou však vyžadovány 3 barvy [1] .

Okraje kompletního grafu s vrcholy mohou být barevně odlišeny, pokud jsou rovné. Toto je speciální případ Baranyaiovy věty . Soifer [2] dává v tomto případě následující geometrickou konstrukci zbarvení: body umístíme do rohů a do středu pravidelného -gonu. Pro každou barevnou třídu vybereme jednu hranu spojující střed a jeden z vrcholů polygonu a všechny hrany na ni kolmé, spojující dvojice vrcholů polygonu. Pokud jsou však liché, jsou vyžadovány barvy – každou barvu lze použít pouze k obarvení hran, -té části všech hran [3] . $K_n$ $n$ $n-1$ $n$ $n$ $(n-1)$ $n$ $n$ $(n-1)/2$ $1/n$

Někteří autoři se zabývali barvením hran lichých grafů , -běžných grafů, ve kterých vrcholy představují týmy hráčů z celkového počtu hráčů a ve kterých okraje představují možné dvojice těchto týmů (s jedním ofsajdovým hráčem na rozhodčím). V případě, že dostaneme známý Petersenův graf . Jak vysvětluje Biggs $n$ $(n-1)$ $2n-1$ $n=3$ [4] , problém (pro) je v tom, že hráči chtějí najít takový rozvrh, aby týmy hrály každý ze šesti zápasů v různé dny v týdnu, s výjimkou neděle pro všechny hráče. V matematické formulaci chtějí najít 6barevné zbarvení čar 6-ti pravidelných grafů. Kdyžse rovná 3, 4 nebo 8, vybarvení čar grafuvyžadujebarvy, ale pro 5, 6 a 7 jsou potřeba pouzebarvy [5] . $n=6$ $O_{6}$ $n$ $Na}$ $n+1$ $n$

Definice

Stejně jako u zbarvení vertexů , obarvení hran grafu, pokud není výslovně uvedeno jinak, vždy předpokládá, že dvěma sousedním hranám jsou přiřazeny různé barvy. Dvě hrany jsou považovány za sousední, pokud mají společný vrchol. Barvení hran grafu lze považovat za ekvivalent zbarvení vrcholu čárového grafu , grafu, který má vrchol pro každou hranu grafu a hranu pro každý pár sousedních hran . $G$ $L(G)$ $G$ $G$

Správné zbarvení různými barvami se nazývá (správné) zbarvení okraje . Pokud lze pro graf najít (správné) zabarvení hran , říká se, že je obarvitelný hranami . Nejmenší počet barev potřebný pro (správné) vybarvení čáry grafu se nazývá chromatický index , neboli hranové chromatické číslo . Chromatický index se někdy zapisuje jako . V tomto zápisu index označuje, že hrany jsou jednorozměrné objekty. Graf je okrajově zbarven, pokud je chromatický index přesně . Chromatický index by neměl být zaměňován s chromatickým číslem nebo s minimálním počtem barev požadovaných ke správnému obarvení vrcholů grafu . $k$ $k$ $k$ $k$ $G$ $\chi {\prime } (G)$ $\chi _{1}(G)$ $k$ $k$ $\chi (G)$ $\chi _{0}(G)$ $G$

Pokud není uvedeno jinak, předpokládá se, že všechny grafy jsou jednoduché, na rozdíl od multigrafů , ve kterých dvě nebo více hran může spojovat stejnou dvojici vrcholů a ve kterých mohou být smyčky (hrana, jejíž koncové vrcholy jsou stejné). U většiny problémů s barvením čar se jednoduché grafy chovají odlišně od multigrafů a při rozšiřování vět o barvení čar z jednoduchých grafů na multigrafy je zapotřebí zvláštní opatrnosti.

Vztah se shodami

Shoda v grafu je množina hran, z nichž žádné dvě nesousedí. Shoda se nazývá dokonalá, pokud její hrany obsahují všechny vrcholy grafu a maximální, pokud obsahuje maximální možný počet hran. Při barvení hran musí být hrany stejné barvy nesousedící, takže tvoří shodu. Správné obarvení hran je tedy stejné jako rozložení grafu na disjunktní párování. $G$

Pokud je velikost maximální shody v daném grafu malá, je potřeba velký počet shod k pokrytí všech okrajů grafu. Formálněji toto vysvětlení předpokládá, že pokud má graf hrany a pokud maximum hran může patřit k maximální shodě, pak každé obarvení hran grafu musí obsahovat alespoň odlišné barvy. [6] Například rovinný graf s 16 vrcholy zobrazený na obrázku má hrany. V tomto grafu neexistuje dokonalá shoda - pokud centrální vrchol patří do shody, lze zbývající vrcholy rozdělit do tří spojených skupin s počtem vrcholů 4, 5, 5. Výsledné podgrafy s lichým počtem vrcholů nemají mít dokonalé sladění. Graf má však maximální shodu se sedmi hranami, takže . Počet barev potřebných pro obarvení hran grafu je tedy alespoň 24/7, a protože počet barev musí být celé číslo, dostaneme alespoň 4 barvy. $m$ $\beta$ $m/\beta$ $m=24$ $\beta=7$

U běžných grafů stupňů , které se dokonale neshodují, lze tuto dolní hranici použít k ukázce, že jsou potřeba alespoň barvy. [6] Zejména to platí pro pravidelné grafy s lichým počtem vrcholů. U takových grafů musí být podle lemmatu handshake , naopak sudé . Nerovnice však plně nevysvětluje chromatický index libovolného pravidelného grafu, protože existují pravidelné grafy, které mají dokonalou shodu, ale nejsou obarvitelné k -hranou . Například Petersenův graf je pravidelný s hranami a s hranami v dokonalé shodě, ale nemá zabarvení hran 3. $k$ $k+1$ $k$ $\chi {\prime }\geqslant m\beta$ $m=15$ $\beta=5$

Vztah s titulem

Vizingova věta

Hranové chromatické číslo grafu úzce souvisí s maximálním stupněm (maximálním počtem hran sousedících s jakýmkoliv jednotlivým vrcholem grafu ). Je jasné, že , takže pokud různé hrany obsahují vrchol , pak musí být všechny tyto hrany obarveny různými barvami, což je možné pouze v případě, že existuje alespoň barev. Vizingova věta (pojmenovaná po Vadimovi Vizingovi , který ji publikoval v roce 1964) říká, že tato hranice je téměř přesná – pro jakýkoli graf je chromatické číslo hrany buď , nebo . Jestliže , G je považováno za třídu 1, jinak se říká, že je třídy 2. $G$ ${\Delta } (G)$ $G$ $\chi {\prime } (G)\geq {\Delta } (G)$ ${\Delta }$ $proti$ $\Delta$ ${\Delta } (G)$ $\Delta (G)+1$ $\chi {\prime }(G)={\Delta }(G)$

Každý bipartitní graf má třídu 1 [7] a téměř všechny náhodné grafy mají třídu 1 [8] . Problém kontroly, zda libovolný graf má třídu 1, je však NP-úplný problém [9] .

Vizing [10] prokázal, že rovinné grafy maximálního stupně alespoň osm mají třídu 1 a domníval se, že totéž platí pro rovinné grafy stupně 7 nebo 6. Na druhé straně existují rovinné grafy s maximálním stupněm mezi dvěma a pěti, které mají třídu 2. Od té doby byla domněnka prokázána pro sedm [11] . Rovinné grafy bez můstků Kubické grafy mají třídu 1, což je ekvivalentní formulaci úlohy čtyř barev [12] .

Regulární grafy

1-faktorizace k - regulárního grafu , tedy rozklad hran grafu na dokonalé shody , je stejná jako zabarvení k -hran grafu. Pravidelný graf má tedy 1-faktorizaci právě tehdy, když má třídu 1. Zvláštní případ, 3-barevné čárové zbarvení kubických (3-běžných) grafů, se někdy nazývá Titeovo zbarvení .

Ne každý běžný graf má 1-faktorizaci. Například Graf Petersen ne. Snarks jsou definovány jako grafy, které jsou stejně jako Petersenův graf bezmůstkové, 3-pravidelné a třídy 2.

Podle Koenigovy věty [7] má každý bipartitní regulární graf 1-faktorizaci. Věta byla formulována dříve v podmínkách projektivních konfigurací a prokázána Ernstem Steinitzem .

Multigrafy

Pro multigrafy , ve kterých více hran může spojovat stejné dva vrcholy, jsou známy podobné, ale slabší výsledky Wiizingova teorému ohledně chromatického čísla hran , maximálního stupně a násobnosti , maximálního počtu hran ve svazku rovnoběžných hran (tj. majících stejné koncové vrcholy). Jako jednoduchý příklad ukazující, že Vizingův teorém nezobecňuje na multigrafy, uvažujme Shannonův multigraf, multigraf se třemi vrcholy a třemi svazky rovnoběžných hran spojujících každou dvojici vrcholů. V tomto příkladu: - každý vrchol sousedí pouze se dvěma ze tří svazků rovnoběžných hran, ale chromatické číslo hrany je (v grafu hran sousedí libovolné dvě hrany, takže všechny hrany musí být obarveny různými barvami). V článku inspirovaném Vizingovým teorémem Soifer a Shannon [13] [14] ukázali, že toto je nejhorší případ pro jakýkoli multigraf . Navíc pro jakýkoli multigraf . Tato nerovnost se redukuje na Vizingovu větu pro jednoduché grafy (pro ně ). $\chi {\prime } (G)$ $\Delta (G)$ $\mu (G)$ $\mu (G)$ $\Delta (G)=2\mu (G)$ $\mu (G)$ $3\mu (G)$ $3\mu (G)$ $\chi {\prime }(G)\leq (3/2)\Delta (G)$ $G$ $G$ $\chi {\prime }(G)\leq \Delta (G)+\mu (G)$ $\u (G) = 1$

Algoritmy

Vzhledem k tomu, že problém kontroly, zda graf má třídu 1, je NP-úplný , neexistuje žádný známý polynomiální-časový algoritmus zbarvení čar pro žádný graf, který poskytuje optimální zbarvení. Byla však vyvinuta řada algoritmů, které oslabují jedno nebo více kritérií: pracují na podmnožině grafů nebo nedávají vždy optimální počet barev nebo ne vždy fungují v polynomiálním čase.

Optimální vybarvení některých speciálních tříd grafů

V případě bipartitních grafů nebo multigrafů s maximálním stupněm je optimální počet barev přesně . V roce 2001 [15] se ukázalo , že optimální vybarvení čar těchto grafů lze nalézt v téměř lineárním čase , kde je počet hran v grafu. Jednodušší, ale poněkud pomalejší algoritmy již dříve popsali Cole a Hopcroft [16] a Alon [17] . Alonův algoritmus začíná tím, že se graf stane pravidelným bez velkého nárůstu stupně nebo velkého zvětšení velikosti sloučením párů vrcholů, které patří do stejné části bipartitního grafu, a poté přidáním malého počtu vrcholů a hran. Poté, pokud je stupeň lichý, Alon najde dokonalou shodu v lineárním čase, přiřadí mu barvu a odstraní ji z grafu, výsledkem je graf sudého stupně. Nakonec Alon používá Gabovovo pozorování [18] , že výběr střídajících se podmnožin hran v Eulerově cyklu grafu jej rozdělí na dva pravidelné podgrafy, čímž se problém zbarvení hran přemění na dva menší problémy, takže jeho algoritmus nyní řeší tyto dva podproblémy rekurzivně . Celková doba běhu algoritmu se odhaduje jako . $\Delta$ $\Delta$ $O(m\,\log\Delta )$ $m$ $O(m\,\log m)$

Pro rovinné grafy s maximálním stupněm je optimální počet barev opět přesně . Za přísnějšího předpokladu, že lze najít optimální zbarvení hran v lineárním čase [19] . ${\Delta}\geq 7$ $\Delta$ ${\Delta}\geq 9$

Algoritmy, které používají více barev, než je potřeba pro optimální vybarvení

Existují polynomiální-časové algoritmy pro obarvení libovolného grafu barvami, což odpovídá hranici dané Vizingovou větou [20] [21] . $\Delta +1$

Pro multigrafy v roce 1987 [22] existuje následující algoritmus (připsaný Eli Upfalovi ): původní multigraf je vytvořen Euler přidáním vrcholu spojeného hranami ke všem vrcholům lichého stupně; je nalezena Eulerova cesta, je zvolena orientace pro tuto cestu; je vytvořen bipartitní graf , který obsahuje dvě kopie každého vrcholu grafu , jednu v každé části, a hrany z vrcholu v levé části k vrcholu v pravé části, když řízená cesta má v grafu oblouk od do . Dále na graf aplikujeme algoritmus pro barvení okraje bipartitního grafu . Každá barva v odpovídá množině hran v , která tvoří podgraf s maximálním stupněm dva, tedy disjunktní spojení cest a cyklů, takže pro každou barvu v , lze vytvořit tři barvy v . Doba běhu algoritmu je omezena dobou barvení bipartitního grafu pomocí algoritmu Colea, Osta a Schirra [15] . Počet barev, které tento algoritmus používá, nepřesahuje , což se blíží, ale ne úplně stejné jako Shannonově hranici . Totéž lze provést přímo s paralelním algoritmem . Ve stejném článku Karloff a Schmois také navrhují algoritmus s lineárním časem pro barvení multigrafů nejvýše třetího stupně čtyřmi barvami (který splňuje jak Shannonovu, tak Weezingovu vazbu). Tento algoritmus funguje na podobných principech – algoritmus také přidá vrchol, aby byl graf eulerovský, najde Eulerovu cestu a poté vybere střídající se sady hran v cestě, aby rozdělil graf na dvě podmnožiny maximálního stupně dva. Cesty a sudé cykly každé podmnožiny lze vybarvit dvěma barvami (dvě barvy na podgraf). Dalším krokem je obarvení hran lichých cyklů, ve kterých může být alespoň jedna hrana obarvena jednou ze dvou barev patřících do protějšího podgrafu. Odstraněním tohoto okraje z lichého cyklu zůstane cesta, kterou lze vybarvit dvěma barvami. $G$ $H$ $G$ $u$ $proti$ $u$ $proti$ $G$ $H$ $H$ $G$ $H$ $G$ $O(m\,\log\Delta )$ $3\levý\lceil {\frac {\Delta }2}\pravý\rceil$ $\left\lfloor {\frac {3\Delta }2}\right\rpatro$

Algoritmus chamtivých barev , který postupně vybírá okraje grafu nebo multigrafu a přiřazuje první platnou barvu, může někdy používat barvy, které mohou být téměř dvojnásobkem požadovaného počtu barev. Má však výhodu v tom, že jej lze použít v online algoritmech , které o struktuře grafu předem nic nevědí. Za těchto podmínek je jeho konkurenční koeficient roven dvěma a tento koeficient je optimální - žádný jiný algoritmus nemůže poskytnout lepší ukazatele [23] . Pokud však hrany přicházejí v náhodném pořadí a původní graf má alespoň logaritmický stupeň, lze získat menší konkurenční koeficient [24] . $2{\Delta }-1$

Někteří autoři předpokládali, že zlomkový chromatický index libovolného multigrafu (číslo, které lze vypočítat v polynomiálním čase pomocí lineárního programování ) se neliší od chromatického indexu o více než jednu [25] . Pokud je domněnka správná, bude možné v případě multigrafů najít číslo, které se neliší od chromatického indexu o více než jedna, což odpovídá Vizingově větě pro jednoduché grafy. Ačkoli v obecném případě se domněnka neprokázala, je známo, že platí, pokud chromatický index není menší než , stejně jako v případě multigrafů s dostatečně velkou multiplicitou [26] . ${\Delta }+{\sqrt {{\Delta }/2))$

Přesné algoritmy

Je snadné zkontrolovat, zda lze graf obarvit okraje jednou nebo dvěma barvami, takže prvním netriviálním případem vybarvení je kontrola, zda lze graf obarvit třemi barvami. V roce 2009 [27] se ukázalo, že je možné ověřit, zda existuje okrajové zbarvení grafu třemi barvami v čase pouze pomocí polynomického prostoru. Ačkoli jsou tyto časové hranice exponenciální, je podstatně rychlejší než vyhledávací algoritmus hrubou silou, protože se dívá na všechna možná zabarvení hran. Jakýkoli dvojitě spojený 3-pravidelný vrcholový graf má 3-hranné zbarvení. A všechny se dají vypsat v čase (o něco pomaleji, než je doba hledání jednoho zbarvení). Jak poznamenal Kuperberg , graf hranolu nad -úhelníkem má mnoho zabarvení, což ukazuje, že tato hranice je přesná [28] . $O(1,344^{n})$ $n$ $O(2^{{n{/2}})$ $O(2^{{n{/2}})$ $n/2$

Použitím přesných algoritmů pro barvení vrcholů spojnicového grafu lze optimálně obarvit okraje libovolného grafu s hranami, bez ohledu na počet potřebných barev, v čase pomocí exponenciálního prostoru nebo v časovém a polynomiálním prostoru [29] . $m$ $2^{m}m^{{O(1)}}$ $O(2,2461^{m})$

Vzhledem k tomu, že problém zbarvení hran je NP-úplný i pro tři barvy, je nepravděpodobné, že se hodí k pevné parametrizaci podle počtu barev. Úloha se však hodí k parametrizaci jinými parametry. Konkrétně Zhou, Nakano a Nishiseki [30] ukázali, že pro grafy šířky stromu lze najít optimální zbarvení čar v čase , který roste exponenciálně od , ale pouze lineárně od počtu vrcholů grafu . $w$ $O(nw(6w)^{{w(w+1)/2}})$ $w$ $n$

V roce 1991 [31] byl problém zbarvení hran formulován jako problém celočíselného programování a byly provedeny experimenty s použitím balíčků celočíselného programování pro obarvení hran grafů, ale nebyla podána žádná analýza složitosti takových algoritmů.

Další vlastnosti

Graf je jedinečně obarvitelný hranami tehdy a jen tehdy, když existuje pouze jeden způsob, jak rozdělit hrany do barevných tříd, nepočítaje možné permutace barev. Pro jedinečně okrajově obarvitelné grafy jsou pouze cesty, cykly a hvězdy , ale pro ostatní grafy mohou být jedinečně hranově obarvitelné. Jakýkoli jedinečně 3hranný obarvitelný graf má přesně tři hamiltonovské cykly (vzniklé odstraněním jedné ze tří barev), ale existují 3 pravidelné grafy, které mají tři hamiltonovské cykly, ale nemají jedinečné 3hranné zbarvení, jako např. zobecněné Petersenovy grafy pro . Je znám pouze jeden nerovinný, jednoznačně 3hranný obarvitelný graf, toto je zobecněný Petersenův graf a existuje domněnka, že žádné jiné neexistují [32] . $k$ $k$ $k!$ $k\neq 3$ $k$ $k = 3$ $k$ $G(6n+3,2)$ $n\geq 2$ $G(9,2)$

Folkman a Fulkerson [33] studovali nerostoucí posloupnosti čísel, pro které existuje obarvení hran daného grafu hranami první barvy, hranami druhé barvy a tak dále. Všimli si, že pokud sekvence sedí v popsaném smyslu a pokud je lexikograficky větší než sekvence se stejným součtem, pak to sedí. Pokud jde o lexikografii, lze jej převést na krok za krokem, v každém kroku zmenšit jedno z čísel o jedničku a zvýšit další číslo ( ) o jedničku. Co se týče barvení hran, začínáme barvením , pak postupně vyměňujeme barvu a v řetězci Kempe nejdelší dráha hran střídajících dvě barvy. Každý graf má zejména zbarvení spravedlivé čáry, zbarvení okraje s optimálním počtem barev, ve kterém se dvě třídy barev liší velikostí nejvýše o jednu. $m_{1},m_{2},m_{3},...$ $G$ $m_1$ $m_2$ $P$ $Q$ $Q$ $P>Q$ $P$ $Q$ $m_i$ $m_{j}$ $i<j$ $P$ $i$ $j$

De Bruijn-Erdősův teorém lze použít k rozšíření mnoha vlastností zbarvení čar z konečných na nekonečné grafy . Například Shannonova a Vizingova věta o vztahu mezi stupněm grafu a jeho chromatickým indexem lze snadno zobecnit na nekonečné grafy [34] .

V roce 2011 [35] se řešil problém najít obrázek daného kubického grafu s vlastnostmi, že všechny hrany na obrázku mají jeden ze tří různých úhlů sklonu a žádné dvě hrany neleží na stejné přímce. Pokud takové znázornění grafu na obrázku existuje, je jasné, že úhel sklonu hran lze považovat za barvu hran při tříbarevném zbarvení grafu. Například vzor hran a dlouhých úhlopříček pravidelného šestiúhelníku představuje hranu 3-zabarvení grafu tímto způsobem. Je ukázáno, že 3-pravidelný bipartitní graf s daným Titeovým zbarvením má grafickou reprezentaci této formy právě tehdy, je -li k-hranně připojen . U nebipartitních grafů je podmínka o něco složitější - dané zbarvení může být reprezentováno takovým vzorem, pokud je dvojitý bipartitní kryt grafu 3-hranně spojený a pokud odstranění dvou stejně barevných hran vede k nebipartitnímu grafu. podgraf. Všechny tyto podmínky lze snadno zkontrolovat v polynomiálním čase, nicméně problém kontroly, zda má 4hranný 4pravidelný graf vzor se čtyřmi sklony odpovídajícími barvám, je pro teorii existence reálných čísel úplný . stejná třída složitosti jako NP-úplnost . $K_{{3,3}}$

V souvislosti s maximálním stupněm a maximálním počtem shod grafu je chromatický index také úzce spjat se stromovitostí grafu , minimálním počtem lineárních lesů (nesouvislý svazek cest), do kterých jsou okraje grafu lze rozdělit. Matching je speciální druh lineárního lesa, ale na druhou stranu každý lineární les může být dvouhranný, takže pro jakýkoli . Akiyamova domněnka uvádí, že , což by znamenalo silnější nerovnost . U grafů maximálního stupně je tři vždy přesně rovno dvěma, takže omezení odpovídá hranici vyplývající z Vizingovy věty [36] . $zpoždění)$ $G$ $G$ $la(G)\leq \chi {\prime }(G)\leq 2la(G)$ ${\mathop {{\mathrm {la}}}} (G)\leq \left\lceil {\frac {{\Delta }+1}{2}}\right\rceil$ $2la(G)-2\leq \chi {\prime }(G)\leq 2la(G)$ $zpoždění)$ $\chi {\prime }(G)\leq 2la(G)$

Jiné typy barvení okrajů

Číslo Thue v grafu je počet barev potřebných pro zbarvení hran, které splňuje silnější požadavek než jakákoli cesta sudé délky, totiž že první a druhá polovina cesty musí tvořit různé sekvence barev.

Stromovitost grafu je minimální počet barev potřebný k vybarvení takovým způsobem, aby okraje žádné barvy neobsahovaly cykly (a nikoli, jako ve standardním problému s vybarvováním, okraje stejné barvy spolu nesousedí). Jedná se tedy o minimální počet prvků lesa , na které lze rozložit okraje grafu [37] . Na rozdíl od chromatického čísla lze šířku lesa vypočítat v polynomiálním čase [38] .

Problém předepsaného zbarvení hran je problém, ve kterém je pro daný graf, pro jehož každý oblouk je uveden seznam barev, nutné najít vhodné zbarvení hran, ve kterém je každá barva převzata z daný seznam. Předepsaný chromatický index grafu je nejmenší číslo, pro které bez ohledu na volbu seznamů barev hran, pokud je každé hraně přiděleno alespoňbarev, je zaručena existence zbarvení. Předepsaný chromatický index není vždy menší než chromatické číslo. Dinitzovu domněnku o vyplnění dílčích latinských čtverců lze přeformulovat jako tvrzení, že předepsané hranové chromatické číslo úplného bipartitního grafu se rovná jeho hranovému chromatickému číslu. V roce 1995 [39] byla domněnka vyřešena a bylo prokázáno silnější tvrzení, že pro jakýkoli bipartitní graf se chromatický index a předepsaný chromatický index rovnají. Ještě obecnější domněnka se uvádí o rovnosti chromatického čísla a předepsaného chromatického čísla pro libovolné multigrafy bez smyček. Tato hypotéza zůstává otevřená. $G$ $k$ $k$ $K_{{n,n}}$ $n$

Mnoho variací problému zbarvení vertexů, které byly studovány, bylo rozšířeno na zbarvení hran. Například problém zbarvení celé hrany je variantou plného zbarvení , správného zbarvení vrcholů, ve kterém musí být jakákoliv dvojice barev přítomna alespoň jednou v sadě sdružených vrcholů, a problémem je maximalizovat celkový počet barvy [40] . Strict edge colouring je varianta strict edge colouring , ve které jakékoliv dvě hrany se sousedními koncovými vrcholy musí mít různé barvy [41] . Striktní zabarvení hran se používá v rozložení kanálů pro bezdrátové sítě [42] . Acyklické čárové zbarvení je varianta acyklického zbarvení , ve kterém libovolné dvě barvy tvoří acyklický podgraf (tj. les) [43] .

V roce 2008 [28] bylo studováno 3-řádkové zbarvení kubických grafů s další vlastností, že žádné dva dvoubarevné cykly nemají více než jednu společnou hranu; konkrétně se ukázalo, že existence takového zbarvení je ekvivalentní existence grafu nakresleného na trojrozměrné celočíselné mřížce s hranami na přímkách rovnoběžných se souřadnicovými osami a každá taková čára obsahuje nejvýše dva vrcholy. Nicméně, stejně jako v případě standardního problému 3-hranného zbarvení, je nalezení zbarvení tohoto typu NP-úplným problémem.

Celkové zbarvení je typ zbarvení, které kombinuje barvení vrcholů a hran, ve kterém jsou obarveny jak vrcholy, tak hrany. Jakýkoli vrchol a hrana, na které je konec, nebo dvě sousední hrany musí mít různé barvy, stejně jako dva sousední vrcholy. Existuje domněnka (kombinující Vizingovu větu a Brooksovu větu ), že každý graf má celkové zbarvení, ve kterém počet barev nepřesahuje maximální mocninu plus dvě. Hypotéza nebyla prokázána.

Je-li 3-běžný graf na ploše obarvitelný 3 hranami, jeho duální graf tvoří triangulaci plochy, která je rovněž hranově obarvitelná (ačkoliv obecně není obarvení čar správné) v tom smyslu, že každý trojúhelník je obarven třemi barvami, jedna hrana na barvu. Jiná zabarvení a orientace trojúhelníků spolu s dalšími místními omezeními, jak jsou barvy rozmístěny ve vrcholech nebo plochách triangulace, lze použít ke kódování určitých typů geometrických objektů. Například pravoúhlé poddělení (části pravoúhlého rozdělení obdélníku na menší obdélníky, kde se v každém bodě setkávají tři obdélníky) lze popsat kombinatoricky „pravidelným značením“, dvoubarevným zabarvením okrajů triangulačního grafu duálním na obdélníkové dělení s omezením, že hrany sousedící s každým vrcholem tvoří čtyři skupiny hran jdoucích (ve směru hodinových ručiček) v řadě. V rámci každé skupiny jsou okraje natřeny stejnou barvou a mají stejný směr. Toto označení je duální vůči zbarvení samotného zjemnění, ve kterém mají svislé okraje jednu barvu a vodorovné okraje jinou. Podobné lokální vazby na pořadí barevných hran pro vrchol lze použít ke kódování vkládání rovinných grafů do mřížky tvořené přímými čarami a 3D mnohostěny s plochami rovnoběžnými s rovinami souřadnic. Pro každý z těchto tří typů pravidelných značek tvoří sada pravidelných značek distribuční mřížku , kterou lze použít k rychlému vyčíslení všech geometrických struktur na základě stejného grafu nebo k nalezení struktury, která splňuje další omezení [44] .

Deterministický konečný automat lze znázornit jako orientovaný graf , ve kterém má každý vrchol stejný přesah vrcholů a ve kterém jsou hrany obarveny takovým způsobem, že jakékoli dvě hrany se stejným počátečním vrcholem mají různé barvy. Problém zbarvení silnice je problém zbarvení čáry pro orientovaný graf se stejným přesahem, takže výsledný automat má synchronizační slovo . Trachtman ( Trachtman 2009 ) vyřešil problém zbarvení silnice tím, že dokázal, že takové zbarvení lze nalézt, pokud je daný graf silně souvislý a aperiodický . $d$

Ramseyův teorém se týká problému barvení okrajů velkého úplného grafu , aby se zabránilo vytváření monochromatických úplných podgrafů nějaké dané velikosti . Podle věty existuje takové číslo , které pro zadané zbarvení není možné. Například , což znamená, že pokud jsou okraje grafu 2barevné, vždy bude existovat monochromatický trojúhelník. $k$ $K_n$ $K_{s}$ $s$ $R_{k}(y)$ $n\geq R(s)$ $R_{2}(3)=6$ $K_{6}$

Aplikace

Barevné čáry kompletních grafů lze použít k rozdělení rozpisu turnajů typu round robin do několika kol tak, aby každá dvojice hrála v jednom z kol. V této aplikaci vrcholy odpovídají účastníkům turnaje a hrany odpovídají hrám. Barva okrajů odpovídá kruhům turnaje [45] . Podobná technika barvení může být použita pro jiné sportovní plány, kde nemusí nutně hrát každý s každým. Například v National Football League (Spojené státy americké, americký fotbal ) jsou dvojice týmů, které budou hrát v daném roce, určeny výsledky týmů v předchozím roce a na graf se použije algoritmus barvení okrajů. tvořená množinou těchto dvojic za účelem distribuce her přes víkend, podle kterých se hry odehrávají [46] . Pro tuto aplikaci Vizingův teorém znamená, že bez ohledu na to, jaká sada párů je zvolena (pokud nehrají dva týmy dvakrát v sezóně), je vždy možné najít rozvrh, který zachycuje maximálně jeden víkend navíc (ve srovnání s počtem her, které hraje jeden tým).

Harmonogram pro otevřenou linku je problém plánování výrobního procesu , ve kterém je mnoho objektů, které je třeba vyrobit. Každý objekt musí projít některými procedurami (v libovolném pořadí) a každá úloha musí být provedena na konkrétním stroji, přičemž stroj může v daný okamžik provádět pouze jednu proceduru. Pokud mají všechny úlohy stejnou délku, pak lze problém položit jako čárové zbarvení bipartitního grafu, ve kterém vrcholy jedné části představují objekty, které mají být vyrobeny, a vrcholy druhé části grafu představují zpracovatelské stroje. . Hrany představují práci, která má být vykonána, a barvy představují časové intervaly, ve kterých musí být práce provedena. Vzhledem k tomu, že čárové zbarvení bipartitního grafu lze provést v polynomiálním čase, totéž platí pro specifikovaný speciální případ plánování otevřené čáry [47] .

V roce 2005 [48] byl studován problém plánování připojení pro komunikační protokol s vícenásobným přístupem s časovým dělením v bezdrátových senzorových sítích jako varianta barvení hran. V tomto problému je potřeba zvolit časové intervaly pro okraje bezdrátové sítě tak, aby každý vrchol sítě mohl komunikovat se sousedními vrcholy bez vzájemného ovlivňování. Použití přísného zbarvení hran (se dvěma časovými rozsahy pro každou barvu hran, jeden v každém směru) problém řeší, ale počet použitých rozsahů může být více, než je nutné. Místo toho hledali zbarvení orientovaného grafu vytvořeného nahrazením každé neorientované hrany dvěma směrovanými oblouky, přičemž každý oblouk měl jinou barvu než barvy oblouků vycházejících z a jeho sousedů . Navrhli heuristický algoritmus pro řešení tohoto problému, založený na distribuovaném algoritmu pro barvení hran , po kterém následuje proces korekce plánu, aby se odstranila možná vzájemná interference. $UV$ $proti$ $proti$ $({\Delta }+1)$

V komunikaci s optickými vlákny je problémem přiřazení barev problém přiřazení světelné frekvence dvojici vrcholů, které vyžadují komunikaci a cesty přes síť vláken pro každý pár, s omezením, že žádné dvě cesty nesdílejí stejný segment vlákna. a stejnou frekvenci. Cesty procházející stejným přepínačem, ale ne přes stejný segment vlákna, mohou mít stejnou frekvenci. Pokud je síť postavena jako hvězda s jediným přepínačem ve středu, který je připojen samostatným vláknem ke každému uzlu sítě, lze problém přiřazení barev modelovat přesně jako problém vybarvování okrajů grafu nebo multigrafu. ve kterých komunikační uzly tvoří uzly grafu, dvojice uzlů, které potřebují výměnu informací, tvoří oblouky a frekvence, kterou lze použít pro každý pár uzlů, odpovídá zabarvení oblouků v problému s vybarvováním. Pro komunikační sítě, které mají obecnější stromovou topologii, mohou být lokální řešení problémů přiřazení barvy cesty hvězdám tvořeným každým komunikátorem spojena za účelem získání jediného globálního řešení [49] .

Otevřené problémy

Jensen a Toft [50] uvedli 23 otevřených problémů týkajících se barvení hran. Tyto zahrnují:

Goldbergova hypotéza [51] , že se chromatický index a zlomkový index neliší o více než jednu, což by umožnilo aproximovat chromatický index s chybou jedné barvy v polynomiálním čase.
Některé Jacobsenovy ( Jakobsenovy ) domněnky a další o struktuře kritických grafů pro vybarvování čar grafů třídy 2 tak, že jakýkoli podgraf má buď nižší maximální stupeň, nebo má třídu 1. Jacobsen původně předpokládal, že všechny kritické grafy mají lichý počet vertices, ale nakonec je předpoklad vyvrácen. Několik dalších domněnek slabších než je tento, stejně jako domněnky omezující počet vrcholů kritických grafů a kritických multigrafů, zůstávají otevřené.
Vizingův problém klasifikace maximálních stupňů, který je možný pro rovinné grafy třídy 2.
Dohad o přetékajících Hiltonových grafech (AJW Hilton), uvádějící, že graf se stupněm má buď třídu 1, nebo obsahuje podgraf stejného stupně jako původní graf, a pro lichý počet vrcholů takový, že počet hran podgraf je větší než . Blízko tomu je domněnka Herberta Grötsche a Paula Seymoura ohledně rovinných grafů namísto grafů vysokého stupně. $n/3$ $\Delta$ $k$ $\Delta(k-1)/2$
Dohad Chetwynda a Hiltona (pravděpodobně zakořeněný v Diracově dřívější práci , že pravidelný graf se sudým počtem vrcholů a stupněm má alespoň třídu 1. $n$ $n/2$
Domněnka Claudy Berge a Delberta Fulkersona , že 6-pravidelné multigrafy vytvořené zdvojením každé hrany 3-pravidelného bezmůstkového jednoduchého grafu lze obarvit šesti barvami.
Fioriniho a Wilsonova domněnka, že žádné rovinné grafy bez trojúhelníků , jiné než dráp K 1,3 , nejsou jednoznačně hranové obarvitelné 3 barvami.

Za zmínku stojí i modernější domněnka: je- li -pravidelný rovinný multigraf, pak je hraně vybarvitelný právě tehdy, je-li spojen s lichou hranou . Tento dohad lze považovat za zobecnění problému čtyř barev pro . Maria Chudnovskaya , Katherine Edwards a Paul Seymour dokázali, že 8-pravidelný planární multigraf má hranové chromatické číslo 8 [52] . $G$ $d$ $G$ $d$ $G$ $d$ $d=3$

Poznámky

↑ Soifer, 2008 , problém 16.4, str. 133.
↑ Soifer, 2008 .
↑ Soifer, 2008 , problém 16.5, str. 133. Skutečnost, že potřebujete buď barvy nebo , vyplývá z Vizingova teorému . $n$ $(n-1)$
↑ Biggs, 1972 .
↑ Biggs, 1972 ; Meredith, Lloyd 1973 ; Biggs, 1979 .
↑ 12 Soifer , 2008 , str. 134.
↑ 1 2 König, 1916 .
↑ Erdős, Wilson, 1977 .
↑ Hollier, 1981 .
↑ Vizing, 1965 .
↑ Sanders, Zhao, 2001 .
↑ Tait, 1880 ; Appel, Haken, 1976 .
↑ Soifer, 2008 , str. 136.
↑ Shannon, 1949 .
↑ 1 2 Cole, Ost, Schirra, 2001 .
↑ Cole, Hopcroft, 1982 .
↑ Alon, 2003 .
↑ Gabov, 1976 .
↑ Cole, Kovalik, 2008 .
↑ Misra, Grise, 1992 .
↑ Gabov a kol., 1985 .
↑ Karlof, Schmois, 1987 .
↑ Bar-Noy, Motwani, Naor, 1992 .
↑ Bahmani, Mehta, Motwani, 2010 .
↑ Goldberg 1973 , Andersen 1977 , Seymour 1979 .
↑ Chen, Yu, Zang, 2011 .
↑ Kovalik, 2009 .
↑ 1 2 Epstein, 2008 .
↑ Björklund, Husfeld, Koivisto, 2009 .
↑ Zhou, Nakano, Nishizeki, 1996 .
↑ Nemhauser, Park, 1991 .
↑ Schwenk, 1989 .
↑ Folkman, Fulkerson, 1969 .
↑ Bosack, 1972 .
↑ Richter, 2011 .
↑ Akiyama, Ikzu, Harari 1980 , Habib, Peroshe 1982 , Horak, Nipel 1982 .
↑ Nash Williams, 1964 .
↑ Gabov, Westerman, 1992 .
↑ Galvin, 1995 .
↑ Bosák, Nešetril, 1976 .
↑ Fouquet, Jolivet 1983 ; Mahdian, 2002 ; Friz, Krivelevich, Sudakov, 2005 ; Cranston, 2006 .
↑ Barret a kol., 2006 .
↑ Alon, Sudakov, Zaks, 2001 , Muthu, Narayanan, Subramanyan, 2007 .
↑ Epstein, 2010 .
↑ Burke, Werra, Kingston, 2004 .
↑ Skiena, 2008 .
↑ Williamson a kol., 1997 .
↑ Gandham, Davande, Prakash, 2005 .
↑ Elebach, Jensen, 2001 .
↑ Jensen, Toft, 1995 .
↑ Goldberg, 1973 .
↑ Maria Chudnovsky, Katherine Edwards, Paul Seymour. Osmipravidelné rovinné grafy zbarvující okraje (neopr.) . - 2012. - 13. ledna.

Odkazy

Jin Akiyama, Geoffrey Exoo, Frank Harary. Krytí a balení v grafech. III. Cyklické a acyklické invarianty // Mathematica Slovaca. - 1980. - T. 30 , no. 4 . - S. 405-417 .
Noga Alon. Jednoduchý algoritmus pro zbarvení hran bipartitních multigrafů // Information Processing Letters. - 2003. - T. 85 , no. 6 . - S. 301-302 . - doi : 10.1016/S0020-0190(02)00446-5 .
Noga Alon, Benny Sudakov, Ayal Zaks. Acyklické obarvení hran grafů // Journal of Graph Theory. - 2001. - T. 37 , no. 3 . - S. 157-167 . - doi : 10.1002/jgt.1010 .
Lars Dovling Andersen. O okrajových zabarveních grafů // Mathematica Scandinavica. - 1977. - T. 40 , čís. 2 . - S. 161-175 . . Jak je uvedeno v [1]
K. Appel, W. Haken. Každá rovinná mapa je čtyřbarevná // Bulletin American Mathematical Society. - 1976. - Sv. 82 , iss. 5 . - str. 711-712 . - doi : 10.1090/S0002-9904-1976-14122-5 .
Bahman Bahmani, Aranyak Mehta, Rajeev Motwani. Sborník příspěvků z 21. výročního sympozia ACM-SIAM o diskrétních algoritmech (SODA '10). - 2010. - S. 31-39 .
Amotz Bar-Noy, Rajeev Motwani, Joseph Naor. Chamtivý algoritmus je optimální pro on-line barvení hran // Information Processing Letters. - 1992. - T. 44 , no. 5 . - S. 251-253 . - doi : 10.1016/0020-0190(92)90209-E .
C. L. Barrett, G. Istrate, V. S. A. Kumar, M. V. Marathe, S. Thite, S. Thulasidasan. Proč. Čtvrtá výroční mezinárodní konference IEEE o Pervasive Computing and Communications Workshops (PerCom Workshops 2006). - 2006. - S. 106 . — ISBN 0-7695-2520-2 . - doi : 10.1109/PERCOMW.2006.129 .
Norman Biggs. Výzkumné problémy / Richard K. Guy. — Americký matematický měsíčník. - 1972. - T. 79. - S. 1018-1020.
Norman Biggs. Druhá mezinárodní konference o kombinatorické matematice // Annals of the New York Academy of Sciences. - 1979. - T. 319 . - S. 71-81 . - doi : 10.1111/j.1749-6632.1979.tb32775.x .
Andreas Bjorklund, Thore Husfeldt, Mikko Koivisto. Nastavení rozdělení pomocí inclusion-exclusion // SIAM Journal on Computing. - 2009. - T. 39 , no. 2 . - S. 546-563 . - doi : 10.1137/070683933 .
Juraj Bosák. Chromatický index konečných a nekonečných grafů // Czechoslovak Mathematical Journal. - 1972. - T. 22 (97) . - S. 272-290 .
Juraj Bosák, Jaroslav Nešetřil. Úplné a pseudokompletní obarvení grafu // Matematicky Casopis Slovenskej Akademie Vied. - 1976. - T. 26 , no. 3 . - S. 171-184 .
E. Burke, D. DeWerra, J. Kingston. {{{title}}} / JL Gross, J. Yellen. - CRC Press, 2004. - S. 462 . - ISBN 978-1-58488-090-5 .
Guantao Chen, Xingxing Yu, Wenan Zang. Aproximace chromatického indexu multigrafů // Journal of Combinatorial Optimization. - 2011. - T. 21 , no. 2 . - S. 219-246 . - doi : 10.1007/s10878-009-9232-y .
Richard Cole, John Hopcroft. Barvení na hraně bipartitních grafů // SIAM Journal on Computing. - 1982. - T. 11 , no. 3 . - S. 540-546 . - doi : 10.1137/0211043 .
Richard Cole, Lukasz Kowalik. Nové algoritmy s lineárním časem pro rovinné grafy s barvením hran // Algorithmica. - 2008. - T. 50 , no. 3 . - S. 351-368 . - doi : 10.1007/s00453-007-9044-3 .
Richard Cole, Kirstin Ost, Stefan Schirra. Hranové bipartitní multigrafy v čase // Combinatorica . - 2001. - T. 21 , no. 1 . - str. 5-12 . - doi : 10.1007/s004930170002 . $O(E\log D)$
Daniel W. Cranston. Silné zabarvení okrajů grafů s maximálním stupněm 4 pomocí 22 barev // Diskrétní matematika . - 2006. - T. 306 , č.p. 21 . - S. 2772-2778 . - doi : 10.1016/j.disc.2006.03.053 .
David Eppstein. Proč. 16th Int. Symp. Grafická kresba / Ioannis G. Tollis, Marizio Patrignani. - Heraklion, Kréta, 2008. - T. 5417. - S. 78-89. — (Poznámky z informatiky).
David Eppstein. Proč. 22. kanadská konference o výpočetní geometrii (CCCG 2010). — 2010.
Paul Erdos, Robin J. Wilson. Poznámka k chromatickému indexu téměř všech grafů // Journal of Combinatorial Theory . - 1977. - T. 23 , no. 2-3 . - S. 255-257 . - doi : 10.1016/0095-8956(77)90039-9 .
Thomas Erlebach, Klaus Jansen. Složitost barvení cest a plánování hovorů // Teoretická informatika. - 2001. - T. 255 , č. 1-2 . - S. 33-50 . - doi : 10.1016/S0304-3975(99)00152-8 .
S. Fiorini, RJ Wilson. Barvení okrajů grafů. - London: Pitman, 1977. - V. 16. - (Research Notes in Mathematics). - ISBN 0-273-01129-4 .
Jon Folkman, D. R. Fulkerson. Kombinatorická matematika a její aplikace (Proc. Conf., Univ. North Carolina, Chapel Hill, NC, 1967). - Chapel Hill, NC: Univ. North Carolina Press, 1969, str. 561-577.
J.L. Fouquet, J.-L. Jolivet. Silné zabarvení hran grafů a aplikací pro víceúhelníky // Ars Combinatoria. - 1983. - T. 16 , no. A. _ - S. 141-150 . $k$
Alan M. Frieze, Michael Krivelevich, Benny Sudakov. Silný chromatický index náhodných grafů // SIAM Journal on Discrete Mathematics . - 2005. - T. 19 , no. 3 . - S. 719-727 (elektronické) . - doi : 10.1137/S0895480104445757 .
Harold N. Gabow. Použití Eulerových oddílů k okrajům barevných bipartitních multigrafů // International Journal of Computer and Information Sciences. - 1976. - V. 5 , čís. 4 . - S. 345-355 . - doi : 10.1007/BF00998632 .
Harold N. Gabow, Takao Nishizeki, Oded Kariv, Daniel Leven, Osamu Terada. Algoritmy pro vybarvování hran grafů. — Univerzita Tohoku, 1985.
Harold N. Gabow, Herbert H. Westermann. Lesy, rámce a hry: algoritmy pro matroidní součty a aplikace // Algorithmica. - 1992. - T. 7 , vydání. 5-6 . - S. 465-497 . - doi : 10.1007/BF01758774 .
F. Galvin. Seznamový chromatický index bipartitního multigrafu // Journal of Combinatorial Theory . - 1995. - T. 63 , no. 1 . - S. 153-158 . - doi : 10.1006/jctb.1995.1011 .
S. Gandham, M. Dawande, R. Prakash. Proč. 24. INFOCOM. - 2005. - T. 4 . - S. 2492-2501 . — ISBN 0-7803-8968-9 . - doi : 10.1109/INFCOM.2005.1498534 .
MK Goldberg. Multigrafy s chromatickým indexem, který je téměř maximální // Diskret. Analyz.. - 1973. - Vydání. 23 . - S. 3-7, 72 . . Jak je uvedeno v [1] .
M. Habib, B. Peroche. Některé problémy o lineární stromořadosti // Diskrétní matematika. - 1982. - T. 41 , no. 2 . - S. 219-220 . - doi : 10.1016/0012-365X(82)90209-6 .
Ian Holyer. NP-úplnost zbarvení hran // SIAM Journal on Computing . - 1981. - T. 10 , no. 4 . - S. 718-720 . - doi : 10.1137/0210055 .
Peter Horák, Ludovit Niepel. Krátký důkaz věty o lineární arboritě pro kubické grafy // Acta Mathematica Universitatis Comeniae. - 1982. - T. 40/41 . - S. 275-277 .
Tommy R. Jensen, Bjarne Toft. Problémy s barvením grafů. - New York: Wiley-Interscience, 1995. - ISBN 0-471-02865-7 .
Howard J. Karloff, David Shmoys. Efektivní paralelní algoritmy pro problémy s barvením hran // Journal of Algorithms. - 1987. - T. 8 , no. 1 . - S. 39-52 . - doi : 10.1016/0196-6774(87)90026-5 .
Uber Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre // Mathematische Annalen . - 1916. - T. 77 , č.p. 4 . - S. 453-465 . - doi : 10.1007/BF01456961 .
Lukasz Kowalík. Vylepšené zbarvení okrajů pomocí tří barev // Teoretická informatika. - 2009. - T. 410 , č.p. 38-40 . - S. 3733-3742 . - doi : 10.1016/j.tcs.2009.05.005 .
Mohammad Mahdian. O výpočetní složitosti silného zbarvení hran // Diskrétní aplikovaná matematika. - 2002. - T. 118 , no. 3 . - S. 239-248 . - doi : 10.1016/S0166-218X(01)00237-2 .
Guy HJ Meredith, E. Keith Lloyd. Fotbalisté Croamu // Journal of Combinatorial Theory . - 1973. - T. 15 , no. 2 . - S. 161-166 . - doi : 10.1016/0095-8956(73)90016-6 .
J. Misra, D. Gries. Konstruktivní důkaz Vizingovy věty // Information Processing Letters . - 1992. - T. 41 , no. 3 . - S. 131-133 . - doi : 10.1016/0020-0190(92)90041-S .
Rahul Muthu, N. Narayanan, C. R. Subramanian. Vylepšené meze acyklického barvení hran // Diskrétní matematika . - 2007. - T. 307 , č.p. 23 . - S. 3063-3069 . - doi : 10.1016/j.disc.2007.03.006 .
Crispin Nash-Williams. Rozklad konečných grafů do lesů // Journal of the London Mathematical Society. - 1964. - T. 39 .
George Nemhauser, park Sungsoo. Polyhedrální přístup k barvení hran // Operations Research Letters. - 1991. - T. 10 , no. 6 . - S. 315-322 . - doi : 10.1016/0167-6377(91)90003-8 .
David A. Richter. Proč. 18th International Symposium on Graph Drawing (GD 2010) / Ulrik Brandes, Sabine Cornelsen. - Springer-Verlag, 2011. - T. 6502. - S. 353-364. — (Poznámky z informatiky). - ISBN 978-3-642-18468-0 . - doi : 10.1007/978-3-642-18469-7_32 .
Daniel P. Sanders, Yue Zhao. Rovinné grafy maximálního stupně sedm jsou třídy I // Journal of Combinatorial Theory . - 2001. - T. 83 , no. 2 . - S. 201-212 . - doi : 10.1006/jctb.2001.2047 .
PD Seymour. O vícebarevnosti kubických grafů a Fulkersonových a Tutteových dohadech // Proceedings of the London Mathematical Society. - 1979. - T. 38 , no. 3 . - S. 423-460 . - doi : 10.1112/plms/s3-38.3.423 .
Allen J. Schwenk. Výčet hamiltonovských cyklů v určitých zobecněných Petersenových grafech // Journal of Combinatorial Theory . - 1989. - T. 47 , no. 1 . - S. 53-59 . - doi : 10.1016/0095-8956(89)90064-6 .
Claude Shannon. Věta o vybarvování čar sítě // J. Math. Fyzika. - 1949. - T. 28 . - S. 148-151 .
Steven S. Skiena. Manuál návrhu algoritmu . - Springer-Verlag, 2008. - S. 548 -550 . - ISBN 978-1-84800-069-8 . - doi : 10.1007/978-1-84800-070-4_16 . . Viz také [1] ve Stony Brook Algorithm Repository.
Alexander Soifer. Matematická omalovánka. - Springer-Verlag, 2008. - ISBN 978-0-387-74640-1 .
PG Tait. Poznámky k barvám map // Proc. R. Soc. Edinburgh. - 1880. - T. 10 . - S. 729 .
Trachtman. Problém zbarvení silnice // Israel Journal of Mathematics. - 2009. - T. 172 , č.p. 1 . - S. 51-60 . - doi : 10.1007/s11856-009-0062-5 . - arXiv : 0709.0099 .
VG Vizáž. O odhadu chromatické třídy p -grafu // Diskret. Analyz .. - 1964. - T. 3 . - S. 25-30 .
VG Vizáž. Kritické grafy s danou chromatickou třídou // Methody Diskret. Analyz.. - 1965. - V. 5 . - S. 9-17 . . (V Rusku.)
DP Williamson, LA Hall, JA Hoogeveen, CAJ Hurkens, JK Lenstra, SV Sevast'janov, DB Shmoys. Krátké rozvrhy obchodů // Operations Research. - 1997. - T. 45 , no. 2 . - S. 288-294 . doi : 10.1287 / opre.45.2.288 . — .
Xiao Zhou, Shin-ichi Nakano, Takao Nishizeki. Částečné -stromy barvení okrajů // Journal of Algorithms. - 1996. - T. 21 , no. 3 . - S. 598-617 . - doi : 10.1006/jagm.1996.0061 . $k$

↑ 1 2 Chen, Yu, Zang, 2011 .