Chamtivé zbarvení - Greedy coloring

Dvě chamtivé barvy stejné korunový graf pomocí různých vrcholných objednávek. Správný příklad zobecňuje na dvoubarevné grafy s

n

vrcholy, kde chamtivý algoritmus utrácí

n /2

barvy.

Ve studii o zbarvení grafu problémy v matematika a počítačová věda, a chamtivé zbarvení nebo postupné zbarvení^[1] je zbarvení vrcholy a graf tvořený a chamtivý algoritmus který bere v úvahu vrcholy grafu v pořadí a každému vrcholu přiřadí jeho první dostupné barva. Chamtivá barviva lze nalézt v lineárním čase, ale obecně nepoužívají minimální možný počet barev.

Různé možnosti posloupnosti vrcholů obvykle vytvoří různá zbarvení daného grafu, takže hodně studia chamtivých barev se zabývalo hledáním dobrého uspořádání. Vždy existuje uspořádání, které produkuje optimální zbarvení, ale i když takové uspořádání lze najít pro mnoho speciálních tříd grafů, je těžké je obecně najít. Běžně používané strategie pro řazení vrcholů zahrnují umístění vrcholů vyšších stupňů dříve než vrcholů nižších stupňů nebo výběr vrcholů s menším počtem dostupných barev, než u méně omezených vrcholů.

Varianty chamtivého zbarvení vyberte barvy v online způsobem, aniž byste věděli o struktuře nebarvené části grafu, nebo zvolte jiné barvy, než jsou první dostupné, abyste snížili celkový počet barev. Na plánování a byly použity algoritmy chamtivého zbarvení přidělení registru problémy, analýza kombinačních her a důkazy o dalších matematických výsledcích včetně Brooksova věta o vztahu mezi zbarvením a stupněm. Mezi další pojmy v teorii grafů odvozené od chamtivých barev patří Zelené číslo grafu (největší počet barev, které lze najít chamtivým zbarvením) a dobře vybarvené grafy, grafy, u nichž všechna chamtivá barvení používají stejný počet barev.

Algoritmus

Chamtivé zbarvení pro dané uspořádání vrcholů lze vypočítat pomocí algoritmus který běží dovnitř lineární čas. Algoritmus zpracovává vrcholy v daném pořadí a každému z nich při zpracování přiřazuje barvu. Barvy mohou být reprezentovány čísly ${displaystyle 0,1,2, tečky}$ a každému vrcholu je dána barva s nejmenší číslo, které ještě není použito jedním z jeho sousedů. Chcete-li najít nejmenší dostupnou barvu, můžete pomocí pole spočítat počet sousedů každé barvy (nebo alternativně reprezentovat sadu barev sousedů) a poté skenováním pole vyhledat index své první nuly.^[2]

v Krajta lze algoritmus vyjádřit jako:

def first_available(color_list):    "" "Vrátit nejmenší nezáporné celé číslo, které není v daném seznamu barev." ""    color_set = soubor(color_list)    počet = 0    zatímco Skutečný:        -li počet ne v color_set:            vrátit se počet        počet += 1        def chamtivý_barva(G, objednat):    "" "Najděte chamtivé zbarvení G v daném pořadí.    Reprezentace G se předpokládá jako https://www.python.org/doc/essays/graphs/    umožňující iteraci sousedů uzlu / vrcholu pomocí „for w in G [node]“.    Návratová hodnota je slovník mapující vrcholy na jejich barvy. "" "    barva = diktát()    pro uzel v objednat:        used_neighbour_colors = [barva[nbr] pro nbr v G[uzel]                                 -li nbr v barva]        barva[uzel] = first_available(used_neighbour_colors)    vrátit se barva

The first_available podprogram trvá čas úměrný délce jeho seznamu argumentů, protože provádí dvě smyčky, jednu přes samotný seznam a jednu přes seznam počtů, které mají stejnou délku. Času pro celkový algoritmus zbarvení dominují volání tohoto podprogramu. Každá hrana v grafu přispívá pouze k jednomu z těchto hovorů, koncovému bodu hrany, který je později v pořadí vrcholů. Součet délek argumentů tedy uvádí first_availablea celkový čas pro algoritmus jsou úměrné počtu hran v grafu.^[2]

Alternativní algoritmus produkující stejné zbarvení,^[3] je vybrat sady vrcholů s každou barvou po jedné. V této metodě každá barevná třída ${displaystyle C}$ je vybráno skenováním vrcholů v daném pořadí. Když toto skenování narazí na nezbarvený vrchol ${displaystyle v}$ který nemá žádného souseda ${displaystyle C}$ , dodává ${displaystyle v}$ na ${displaystyle C}$ . Takto, ${displaystyle C}$ se stává maximální nezávislá množina mezi vrcholy, kterým ještě nebyly přiřazeny menší barvy. Algoritmus tímto způsobem opakovaně vyhledává barevné třídy, dokud nejsou vybarveny všechny vrcholy. Zahrnuje však provedení více skenů grafu, jednoho skenování pro každou barevnou třídu, místo výše uvedené metody, která používá pouze jeden sken.^[4]

Možnost objednání

Různé uspořádání vrcholů grafu může způsobit, že chamtivé zbarvení použije různé počty barev, od optimálního počtu barev až po v některých případech počet barev, který je úměrný počtu vrcholů v grafu. instance, a korunový graf (graf vytvořený ze dvou disjunktní sady z $n /2$ vrcholy ${A 1, A 2, ...$ } a ${b 1, b 2, ...$ } připojením $A i$ na $b j$ kdykoli $i \neq j$ ) může být obzvláště špatným případem pro chamtivé zbarvení. S objednáváním vrcholů $A 1, b 1, A 2, b 2, ...$ , použije se chamtivé zbarvení $n /2$ barvy, jedna barva pro každý pár $(A i, b i)$ . Optimální počet barev pro tento graf je však dvě, jedna barva pro vrcholy $A i$ a další pro vrcholy $b i$ .^[5] Existují také grafy, že s vysokou pravděpodobností náhodně zvolené řazení vrcholů vede k množství barev mnohem větších, než je minimum.^[6] Proto je v chamtivém zbarvení důležitý pečlivý výběr pořadí vrcholů.

Dobré objednávky

Vrcholy libovolného grafu lze vždy uspořádat tak, aby chamtivý algoritmus vytvořil optimální zbarvení. Pro dané optimální zbarvení je možné vrcholy řadit podle jejich barev. Když tedy člověk použije chamtivý algoritmus s tímto řádem, je výsledné vybarvení automaticky optimální.^[7] Protože však optimální zbarvení grafu je NP-kompletní, jakýkoli dílčí problém, který by umožnil rychlé vyřešení tohoto problému, včetně nalezení optimálního uspořádání pro chamtivé zbarvení, je NP-tvrdé.^[8]

v intervalové grafy a chordální grafy, jsou-li vrcholy uspořádány v obráceném pořadí a perfektní objednávka eliminace, pak dřívější sousedé každého vrcholu vytvoří a klika. Tato vlastnost způsobí, že chamtivé zbarvení vytvoří optimální zbarvení, protože nikdy nepoužívá více barev, než je požadováno pro každou z těchto klik. Pořadí eliminace lze nalézt v lineárním čase, pokud existuje.^[9]

Silnější je jakékoli dokonalé objednávání eliminace dědičně optimální, což znamená, že je optimální jak pro samotný graf, tak pro všechny jeho indukované podgrafy. The dokonale uspořádatelné grafy (který zahrnuje chordální grafy, srovnatelné grafy, a vzdálenostně dědičné grafy ) jsou definovány jako grafy, které mají dědičně optimální řazení.^[10] Rozpoznávání dokonale uspořádatelných grafů je také NP-úplné.^[11]

Špatné objednávky

Počet barev produkovaných chamtivým zbarvením pro nejhorší pořadí daného grafu se nazývá jeho Zelené číslo.^[12]Stejně jako je obtížné najít dobré pořadí vrcholů pro chamtivé zbarvení, je obtížné najít i špatné uspořádání vrcholů. Pro daný graf je určování NP úplné. $G$ a číslo $k$ , zda existuje uspořádání vrcholů $G$ který způsobí použití chamtivého algoritmu $k$ nebo více barev. To zejména znamená, že je obtížné najít nejhorší objednávku $G$ .^[12]

Grafy, pro které je pořadí irelevantní

The dobře vybarvené grafy jsou grafy, u nichž všechna barevná provedení vrcholů produkují stejný počet barev. Tento počet barev se v těchto grafech rovná chromatickému číslu i Grundovu číslu.^[12] Zahrnují cographs, což jsou přesně grafy, ve kterých jsou všechny indukované podgrafy jsou dobře vybarvené.^[13] Ale je co-NP-kompletní k určení, zda je graf dobře zbarvený.^[12]

Pokud náhodný graf je čerpáno z Erdős – Rényiho model s konstantní pravděpodobností zahrnutí každé hrany, pak jakékoli uspořádání vrcholů, které je zvoleno nezávisle na hranách grafu, vede k vybarvení, jehož počet barev se blíží dvojnásobku optimální hodnoty, s vysokou pravděpodobností Zůstává neznámé, zda existuje metoda polynomiálního času pro nalezení výrazně lepšího zabarvení těchto grafů.^[3]

Degenerace

Trojúhelníkový hranol a čtvercový antiprism, grafy, jejichž chamtivé barvy využívající pořadí degenerace dávají větší než optimální počet barev

Protože je obtížné najít optimální uspořádání vrcholů, byla použita heuristika, která se pokouší snížit počet barev, aniž by zaručila optimální počet barev. Běžně používaným uspořádáním pro chamtivé zbarvení je výběr vrcholu $proti$ minima stupeň, objednejte podgraf s $proti$ odstraněn rekurzivně a poté umístěte $proti$ poslední v objednávce. Největší stupeň odstraněného vrcholu, se kterým se tento algoritmus setkává, se nazývá zvrhlost grafu, označeno $d$ . V kontextu chamtivého zbarvení se stejná strategie objednávání nazývá také nejmenší poslední objednávka.^[14] Toto uspořádání vrcholů a degeneraci lze vypočítat v lineárním čase.^[15]Lze jej zobrazit jako vylepšenou verzi dřívější metody řazení vrcholů, největšího prvního řazení, která třídí vrcholy v sestupném pořadí podle jejich stupňů.^[16]

Při objednávání degenerace bude chamtivé zbarvení použito nanejvýš $d + 1$ barvy. Je to proto, že pokud budou zbarveny, každý vrchol bude mít maximálně $d$ již vybarvené sousedy, takže jeden z prvních $d + 1$ barvy budou pro použití zdarma.^[17] Chamtivé zbarvení s uspořádáním degenerace může najít optimální zbarvení pro určité třídy grafů, včetně stromů, pseudolesy a korunové grafy.^[18] Markossian, Gasparian & Reed (1996) definovat graf ${displaystyle G}$ být ${displaystyle eta}$ -dokonalé, pokud, pro ${displaystyle G}$ a každý indukovaný podgraf z ${displaystyle G}$ , chromatické číslo se rovná degeneraci plus jedna. U těchto grafů je vždy optimální chamtivý algoritmus s uspořádáním degenerace.^[19]Každý ${displaystyle eta}$ -perfektní graf musí být rovnoměrný graf bez děr, protože i cykly mají chromatické číslo dvě a degeneraci dvě, neodpovídající rovnosti v definici ${displaystyle eta}$ -dokonalé grafy. Pokud graf a jeho doplňkový graf jsou oba bez děr, jsou oba ${displaystyle eta}$ -perfektní. Grafy, které jsou oba perfektní grafy a ${displaystyle eta}$ -dokonalé grafy jsou přesně chordální grafy. Na grafech bez rovnoměrných děr obecně se pořadí degenerace přibližuje optimálnímu zbarvení maximálně dvojnásobku optimálního počtu barev; to je jeho přibližný poměr je 2.^[20] Na jednotkové diskové grafy jeho přibližný poměr je 3.^[21] The trojúhelníkový hranol je nejmenší graf, u kterého jedno z jeho degenerovaných uspořádání vede k neoptimálnímu zabarvení, a čtvercový antiprism je nejmenší graf, který nelze optimálně obarvit pomocí žádného z jeho degeneračních uspořádání.^[18]

Adaptivní objednávky

Brélaz (1979) navrhuje strategii, tzv DSatur, pro řazení vrcholů v chamtivém zbarvení, které prokládá konstrukci uspořádání s procesem barvení. Ve své verzi algoritmu chamtivého zbarvení je vybrán další vrchol, který má být zbarven v každém kroku, jako ten s největším počtem odlišných barev v jeho sousedství. V případě vazeb je ze svázaných vrcholů vybrán vrchol maximálního stupně v podgrafu nezbarvených vrcholů. Sledováním sad sousedních barev a jejich kardinality v každém kroku je možné tuto metodu implementovat v lineárním čase.^[22]

Tato metoda může najít optimální barviva pro bipartitní grafy,^[23] Všechno kaktusové grafy, Všechno grafy kol, všechny grafy na maximálně šesti vrcholech a skoro každý ${displaystyle k}$ -barevný graf.^[24] Ačkoli Lévêque & Maffray (2005) původně tvrdil, že tato metoda najde optimální zbarvení pro Meyniel grafy, později našli protiklad tohoto tvrzení.^[25]

Alternativní schémata výběru barev

Je možné definovat varianty algoritmu chamtivého zbarvení, ve kterém jsou vrcholy daného grafu vybarveny v dané sekvenci, ale ve kterých barva vybraná pro každý vrchol nemusí být nutně první dostupnou barvou. Patří mezi ně metody, ve kterých je nezbarvená část grafu algoritmu neznámá, nebo ve kterých je algoritmu dána určitá volnost, aby mohl lépe vybírat barvy než základní chamtivý algoritmus.

Online výběr

Alternativní strategie výběru barev byly studovány v rámci online algoritmy. V online problému s barvením grafů jsou vrcholy grafu prezentovány jeden po druhém v libovolném pořadí podle algoritmu barvení; algoritmus musí zvolit barvu pro každý vrchol, pouze na základě barev a sousedství mezi již zpracovanými vrcholy. V této souvislosti se měří kvalita strategie výběru barev podle ní konkurenční poměr, poměr mezi počtem barev, které používá, a optimálním počtem barev pro daný graf.^[26]

Pokud v grafu nejsou uvedena žádná další omezení, je optimální konkurenční poměr jen mírně sublineární.^[27] Nicméně pro intervalové grafy, je možný stálý konkurenční poměr,^[28] zatímco pro bipartitní grafy a řídké grafy lze dosáhnout logaritmického poměru. Ve skutečnosti pro řídké grafy standardní chamtivá barevná strategie výběru první dostupné barvy dosahuje tohoto konkurenčního poměru a je možné prokázat odpovídající spodní hranici konkurenčního poměru jakéhokoli online algoritmu zbarvení.^[26]

Šetrné zbarvení

A šetrné zbarvení, pro dané uspořádání grafů a vrcholů bylo definováno jako zbarvení vytvořené chamtivým algoritmem, který vybarví vrcholy v daném pořadí, a zavádí novou barvu pouze tehdy, když všechny předchozí barvy sousedí s daným vrcholem, ale mohou si vybrat jakou barvu použít (místo toho, aby vždy vybrala nejmenší), když je schopna znovu použít existující barvu. The objednané chromatické číslo je nejmenší počet barev, které lze získat pro dané pořadí tímto způsobem, a ochromatické číslo je největší uspořádané barevné číslo mezi všemi barvami vrcholů daného grafu. Přes svou odlišnou definici se ochromatické číslo vždy rovná Grundovu číslu.^[29]

Aplikace

Protože je to rychlé a v mnoha případech lze použít jen málo barev, lze chamtivé vybarvení použít v aplikacích, kde je potřeba dobré, ale ne optimální vybarvení grafu. Jednou z prvních aplikací chamtivého algoritmu bylo řešení problémů, jako je plánování kurzů, při kterém musí být skupině úkolů přiřazena určitá sada časových úseků, aby se zabránilo přiřazení nekompatibilních úkolů stejnému časovému úseku.^[4]Může být také použit v překladače pro přidělení registru tím, že ji použijeme na graf, jehož vrcholy představují hodnoty, které mají být přiřazeny registrům a jejichž hrany představují konflikty mezi dvěma hodnotami, které nelze přiřadit ke stejnému registru.^[30] V mnoha případech jsou tyto interferenční grafy chordální grafy, umožňující chamtivé zbarvení k vytvoření optimálního přiřazení registru.^[31]

v kombinatorická teorie her, pro nestranná hra uveden v explicitní formě jako směrovaný acyklický graf jehož vrcholy představují herní pozice a jejichž hrany představují platné tahy z jedné polohy do druhé, chamtivý algoritmus zbarvení (pomocí reverzu topologické uspořádání grafu) vypočítá nim-hodnota každé pozice. Tyto hodnoty lze použít k určení optimální hry v jakékoli jednotlivé hře disjunktivní částka her.^[32]

Pro graf maximálního stupně $Δ$ , použije se maximálně jakékoli chamtivé zbarvení $Δ + 1$ barvy. Brooksova věta uvádí, že až na dvě výjimky (kliky a liché cykly ) nejvíce $Δ$ barvy jsou potřeba. Jeden důkaz Brooksovy věty zahrnuje nalezení uspořádání vrcholů, ve kterém první dva vrcholy sousedí s posledním vrcholem, ale ne sousedí navzájem a každý vrchol kromě posledního má alespoň jednoho pozdějšího souseda. Pro objednávání s touto vlastností používá algoritmus chamtivého zbarvení nanejvýš $Δ$ barvy.^[33]

Poznámky

^ Mitchem (1976).
^ ^A ^b Hoàng & Sritharan (2016), Věta 28.33, str. 738; Husfeldt (2015), Algoritmus G.
^ ^A ^b Frieze & McDiarmid (1997).
^ ^A ^b Welsh & Powell (1967).
^ Johnson (1974); Husfeldt (2015).
^ Kučera (1991); Husfeldt (2015).
^ Husfeldt (2015).
^ Maffray (2003).
^ Rose, Lueker & Tarjan (1976).
^ Chvátal (1984); Husfeldt (2015).
^ Middendorf & Pfeiffer (1990).
^ ^A ^b ^C ^d Zaker (2006).
^ Christen & Selkow (1979).
^ Mitchem (1976); Husfeldt (2015).
^ Matula & Beck (1983).
^ Welsh & Powell (1967); Husfeldt (2015).
^ Matula (1968); Szekeres & Wilf (1968).
^ ^A ^b Kosowski & Manuszewski (2004).
^ Markossian, Gasparian & Reed (1996); Maffray (2003).
^ Markossian, Gasparian & Reed (1996).
^ Gräf, Stumpf & Weißenfels (1998).
^ Brélaz (1979); Lévêque & Maffray (2005).
^ Brélaz (1979).
^ Janczewski a kol. (2001).
^ Lévêque & Maffray (2005).
^ ^A ^b Irani (1994).
^ Lovász, Saks & Trotter (1989); Vishwanathan (1992).
^ Kierstead a Trotter (1981).
^ Simmons (1982); Erdős a kol. (1987).
^ Poletto & Sarkar (1999). Ačkoli Poletto a Sarkar popisují svoji metodu přidělování registrů jako nevycházející z zbarvení grafu, zdá se, že je stejná jako chamtivé zbarvení.
^ Pereira a Palsberg (2005).
^ Např. Viz oddíl 1.1 Nivasch (2006).
^ Lovász (1975).

Reference

Brélaz, Daniel (duben 1979), „Nové metody vybarvení vrcholů grafu“, Komunikace ACM, 22 (4): 251–256, doi:10.1145/359094.359101
Christen, Claude A .; Selkow, Stanley M. (1979), „Některé dokonalé barevné vlastnosti grafů“, Journal of Combinatorial Theory, Řada B, 27 (1): 49–59, doi:10.1016/0095-8956(79)90067-4, PAN 0539075
Chvátal, Václav (1984), "Perfectly orderable graphs", in Berge, Claude; Chvátal, Václav (eds.), Témata v dokonalých grafech, Annals of Discrete Mathematics, 21, Amsterdam: Severní Holandsko, s. 63–68. Jak uvádí Maffray (2003).
Erdős, P.; Hare, W. R .; Hedetniemi, S. T .; Laskar, R. (1987), „O rovnosti zeleného a ochromatického čísla grafu“ (PDF), Journal of Graph Theory, 11 (2): 157–159, doi:10.1002 / jgt.3190110205, PAN 0889347.
Vlys, Alan; McDiarmid, Colin (1997), „Algoritmická teorie náhodných grafů“, Náhodné struktury a algoritmy, 10 (1–2): 5–42, doi:10.1002 / (SICI) 1098-2418 (199701/03) 10: 1/2 <5 :: AID-RSA2> 3.3.CO; 2-6, PAN 1611517.
Gräf, A .; Stumpf, M .; Weißenfels, G. (1998), „On colored unit disk graphs“, Algorithmica, 20 (3): 277–293, doi:10.1007 / PL00009196, PAN 1489033.
Hoàng, Chinh T .; Sritharan, R. (2016), „Kapitola 28. Perfect Graphs“, Thulasiraman, Krishnaiyan; Arumugam, Subramanian; Brandstädt, Andreas; Nishizeki, Takao (eds.), Příručka teorie grafů, kombinatorické optimalizace a algoritmů, Chapman & Hall / CRC Series of Computer and Information Science Series, 34, CRC Press, str. 707–750, ISBN 9781420011074.
Husfeldt, Thore (2015), „Algoritmy barvení grafů“, Beineke, Lowell W .; Wilson, Robin J. (eds.), Témata v teorii chromatických grafůEncyklopedie matematiky a její aplikace, 156, Cambridge University Press, s. 277–303, arXiv:1505.05825, PAN 3380176
Irani, Sandy (1994), „Coloring inductive graphs on-line“, Algorithmica, 11 (1): 53–72, doi:10.1007 / BF01294263, PAN 1247988.
Janczewski, R .; Kubale, M .; Manuszewski, K .; Piwakowski, K. (2001), „Nejmenší barevný graf pro algoritmus DSATUR“, Diskrétní matematika, 236 (1–3): 151–165, doi:10.1016 / S0012-365X (00) 00439-8, PAN 1830607.
Kierstead, H. A .; Trotter, W. T. (1981), „Extrémní problém rekurzivní kombinatoriky“, Proceedings of the Twelfth Southeastern Conference on Combinatorics, Graph Theory and Computing, Vol. II (Baton Rouge, La., 1981), Congressus Numerantium, 33: 143–153, PAN 0681909. Jak uvádí Irani (1994).
Kosowski, Adrian; Manuszewski, Krzysztof (2004), „Classical colored of graphs“, in Kubale, Marek (ed.), Barvení grafů, Současná matematika, 352„Providence, Rhode Island: American Mathematical Society, s. 1–19, doi:10.1090 / conm / 352/06369, PAN 2076987
Kučera, Luděk (1991), „Chamtivé zbarvení je špatný pravděpodobnostní algoritmus“, Journal of Algorithms, 12 (4): 674–684, doi:10.1016/0196-6774(91)90040-6, PAN 1130323.
Johnson, David S. (1974), „Nejhorší chování algoritmů barvení grafů“, Proceedings of the Fifth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1974), Congressus Numerantium, X„Winnipeg, Manitoba: Utilitas Math., S. 513–527, PAN 0389644.
Lévêque, Benjamin; Maffray, Frédéric (říjen 2005), "Zbarvení Meyniel grafů v lineárním čase" (PDF)v Raspaud, André; Delmas, Olivier (eds.), 7. mezinárodní kolokvium o teorii grafů (ICGT '05), 12. – 16. Září 2005, Hyeres, Francie, Elektronické poznámky v diskrétní matematice, 22, Elsevier, s. 25–28, arXiv:cs / 0405059, doi:10.1016 / j.endm.2005.06.005. Viz také Lévêque, Benjamin; Maffray, Frédéric (9. ledna 2006), Chyba: MCColor není v grafech Meyniel optimální, arXiv:cs / 0405059.
Lovász, L. (1975), „Tři krátké důkazy v teorii grafů“, Journal of Combinatorial Theory, Řada B, 19 (3): 269–271, doi:10.1016/0095-8956(75)90089-1, PAN 0396344.
Lovász, L.; Saks, M. E.; Trotter, W. T. (1989), „On-line algoritmus barvení grafů s sublearním výkonovým poměrem“, Diskrétní matematika, 75 (1–3): 319–325, doi:10.1016 / 0012-365X (89) 90096-4, PAN 1001404.
Maffray, Frédéric (2003), „O zbarvení dokonalých grafů“, v Reed, Bruce A.; Prodej, Cláudia L. (eds.), Nedávné pokroky v algoritmech a kombinatoriceKnihy CMS z matematiky, 11, Springer-Verlag, str. 65–84, doi:10.1007/0-387-22444-0_3, ISBN 0-387-95434-1, PAN 1952983.
Markossian, S.E .; Gasparian, G. S .; Reed, B. A. (1996), „β-perfect graphs“, Journal of Combinatorial Theory, Řada B, 67 (1): 1–11, doi:10.1006 / jctb.1996.0030, PAN 1385380.
Matula, David W. (1968), „Věta min-max pro grafy s aplikací na zbarvení grafů“, Národní setkání SIAM 1968, Recenze SIAM, 10 (4): 481–482, doi:10.1137/1010115.
Matula, David W .; Beck, L. L. (1983), „Nejmenší-poslední řazení a shlukování a algoritmy barvení grafů“, Deník ACM, 30 (3): 417–427, doi:10.1145/2402.322385, PAN 0709826.
Middendorf, Matthias; Pfeiffer, Frank (1990), „O složitosti rozpoznávání dokonale uspořádaných grafů“, Diskrétní matematika, 80 (3): 327–333, doi:10.1016 / 0012-365X (90) 90251-C, PAN 1049253.
Mitchem, John (1976), „O různých algoritmech pro odhad chromatického čísla grafu“, Počítačový deník, 19 (2): 182–183, doi:10.1093 / comjnl / 19.2.182, PAN 0437376.
Nivasch, Gabriel (2006), „Funkce Sprague – Grundy hry Euclid“, Diskrétní matematika, 306 (21): 2798–2800, doi:10.1016 / j.disc.2006.04.020, PAN 2264378.
Pereira, Fernando Magno Quintão; Palsberg, Jens (2005), „Alokace registrů pomocí vybarvení chordálních grafů“, Yi, Kwangkeun (ed.), Programovací jazyky a systémy: Third Asian Symposium, APLAS 2005, Tsukuba, Japan, 2. – 5. Listopadu 2005, sborník, Přednášky v informatice, 3780, Springer, str. 315–329, doi:10.1007/11575467_21
Poletto, Massimiliano; Sarkar, Vivek (září 1999), „Přidělení registru lineárního skenování“, Transakce ACM v programovacích jazycích a systémech, 21 (5): 895–913, doi:10.1145/330249.330250.
Rose, D .; Lueker, George; Tarjan, Robert E. (1976), „Algoritmické aspekty eliminace vrcholů v grafech“, SIAM Journal on Computing, 5 (2): 266–283, doi:10.1137/0205021, PAN 0408312.
Simmons, Gustavus J. (1982), „Objednané chromatické množství planárních map“, Sborník ze třinácté jihovýchodní konference o kombinatorice, teorii grafů a výpočtech (Boca Raton, Fla., 1982), Congressus Numerantium, 36: 59–67, PAN 0726050
Sysło, Maciej M. (1989), „Sekvenční zbarvení versus vazba Welsh-Powell“, Diskrétní matematika, 74 (1–2): 241–243, doi:10.1016 / 0012-365X (89) 90212-4, PAN 0989136.
Szekeres, George; Wilf, Herbert S. (1968), „Nerovnost chromatického čísla grafu“, Journal of Combinatorial Theory, 4: 1–3, doi:10.1016 / S0021-9800 (68) 80081-X.
Vishwanathan, Sundar (1992), „Randomizované online zbarvení grafů“, Journal of Algorithms, 13 (4): 657–669, doi:10.1016 / 0196-6774 (92) 90061-G, PAN 1187207.
Velština, D. J. A.; Powell, M. B. (1967), „Horní hranice pro chromatické číslo grafu a jeho použití na problémy s rozvrhováním času“, Počítačový deník, 10 (1): 85–86, doi:10.1093 / comjnl / 10.1.85.
Zaker, Manouchehr (2006), „Výsledky na Grundyově chromatickém počtu grafů“, Diskrétní matematika, 306 (2–3): 3166–3173, doi:10.1016 / j.disc.2005.06.044, PAN 2273147.

[FOOTNOTEMitchem1976-1] Mitchem (1976).

[hs-2] A ^b Hoàng & Sritharan (2016), Věta 28.33, str. 738; Husfeldt (2015), Algoritmus G.

[FOOTNOTEFriezeMcDiarmid1997-3] A ^b Frieze & McDiarmid (1997).

[FOOTNOTEWelshPowell1967-4] A ^b Welsh & Powell (1967).

[5] Johnson (1974); Husfeldt (2015).

[6] Kučera (1991); Husfeldt (2015).

[FOOTNOTEHusfeldt2015-7] Husfeldt (2015).

[FOOTNOTEMaffray2003-8] Maffray (2003).

[FOOTNOTERoseLuekerTarjan1976-9] Rose, Lueker & Tarjan (1976).

[10] Chvátal (1984); Husfeldt (2015).

[FOOTNOTEMiddendorfPfeiffer1990-11] Middendorf & Pfeiffer (1990).

[FOOTNOTEZaker2006-12] A ^b ^C ^d Zaker (2006).

[FOOTNOTEChristenSelkow1979-13] Christen & Selkow (1979).

[14] Mitchem (1976); Husfeldt (2015).

[FOOTNOTEMatulaBeck1983-15] Matula & Beck (1983).

[16] Welsh & Powell (1967); Husfeldt (2015).

[17] Matula (1968); Szekeres & Wilf (1968).

[FOOTNOTEKosowskiManuszewski2004-18] A ^b Kosowski & Manuszewski (2004).

[19] Markossian, Gasparian & Reed (1996); Maffray (2003).

[FOOTNOTEMarkossianGasparianReed1996-20] Markossian, Gasparian & Reed (1996).

[FOOTNOTEGräfStumpfWeißenfels1998-21] Gräf, Stumpf & Weißenfels (1998).

[22] Brélaz (1979); Lévêque & Maffray (2005).

[FOOTNOTEBrélaz1979-23] Brélaz (1979).

[FOOTNOTEJanczewskiKubaleManuszewskiPiwakowski2001-24] Janczewski a kol. (2001).

[FOOTNOTELévêqueMaffray2005-25] Lévêque & Maffray (2005).

[FOOTNOTEIrani1994-26] A ^b Irani (1994).

[27] Lovász, Saks & Trotter (1989); Vishwanathan (1992).

[FOOTNOTEKiersteadTrotter1981-28] Kierstead a Trotter (1981).

[29] Simmons (1982); Erdős a kol. (1987).

[30] Poletto & Sarkar (1999). Ačkoli Poletto a Sarkar popisují svoji metodu přidělování registrů jako nevycházející z zbarvení grafu, zdá se, že je stejná jako chamtivé zbarvení.

[FOOTNOTEPereiraPalsberg2005-31] Pereira a Palsberg (2005).

[32] Např. Viz oddíl 1.1 Nivasch (2006).

[FOOTNOTELovász1975-33] Lovász (1975).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]