Jednotné zbarvení

Jednotné zbarvení  je přiřazení barev k vrcholům neorientovaného grafu takovým způsobem, že:

To znamená, že rozdělení vrcholů do různých barev je co nejrovnoměrnější. Například dát každému vrcholu jinou barvu by bylo jednotné zbarvení, ale obvykle by se použilo mnohem více barev, než je potřeba pro optimální jednotné zbarvení. Ekvivalentní způsob, jak definovat jednotné zbarvení, je vložit daný graf jako podgraf do grafu Turan se stejnou sadou vrcholů. Existují dva druhy chromatických čísel spojených s jednotným zbarvením [1] . Jednotné chromatické číslo grafu G  je nejmenší číslo k , takže graf G má jednotné zabarvení sk barev. U některých větších sad barev však graf G nemusí mít jednotné zabarvení. Jednotný chromatický práh grafu G  je nejmenší číslo k , takže graf G má jednotné zabarvení pro libovolný počet barev větší nebo rovný k [2] .

Hajnal-Szemeredy teorém , který byl formulován jako domněnka Palem Erdősem [3] a dokázán Andrásem Hajnalem a Endrem Szemeredym [4] , uvádí, že každý graf s maximálním stupněm má jednotné zabarvení barvami. Několik souvisejících hypotéz zůstává otevřených. Existují také polynomiální časové algoritmy pro nalezení zabarvení odpovídající této hranici [5] , stejně jako algoritmy pro nalezení optimálního zabarvení pro speciální třídy grafů, ale obecnější problém určení, zda libovolný graf má jednotné zabarvení s daným počet barev je NP-úplný .

Příklady

Hvězda K 1,5 zobrazená na obrázku je úplný bipartitní graf , a proto může být vybarven dvěma barvami. Výsledné zbarvení má však jeden vrchol jedné barvy a pět vrcholů jiné barvy, a proto není zbarvení jednotné. Nejmenší počet barev v jednotném vybarvení tohoto grafu jsou čtyři, jak je znázorněno na obrázku - centrální vrchol musí patřit do třídy s jedním vrcholem, takže dalších pět vrcholů musí být rozděleno alespoň na tři barvy tak, aby každý třída obsahuje nejvýše dva vrcholy. Obecněji, Meyer [6] poznamenal, že každá hvězda K 1, n vyžaduje barvy pro jednotné zbarvení, a proto se chromatické číslo grafu může lišit od jeho chromatického jednotného čísla o ne více než n /4krát. Protože K 1,5 má maximální stupeň pět, počet barev zaručený Hajnal-Szemerediho teorémem je šest, což se získá přiřazením jiné barvy každému vrcholu.

Další zajímavý jev ukazuje další úplný bipartitní graf, . Tento graf má jednotné 2 zbarvení definované jeho bipartitou. Nemá však jednotné (2 n  + 1) zabarvení - jakékoli jednotné rozdělení vrcholů na tento počet barev by muselo mít přesně dva vrcholy na barvu, ale dvě části bipartitního grafu nelze spárovat, protože obsahují lichý počet vrcholů. Proto je jednotný chromatický práh tohoto grafu , který je mnohem větší než jeho jednotné chromatické číslo, které je dva.

Hainal-Semerediho věta

Brooksův teorém říká, že každý souvislý graf s maximálním stupněm je -barvitelný, se dvěma výjimkami ( úplné grafy a liché cykly). Toto zbarvení však obecně nemusí být jednotné. Pal Erdős [3] předpokládal, že jednotné zbarvení je možné pouze s jednou doplňkovou barvou – každý graf s maximálním stupněm má jednotné zbarvení s barvami. Pouzdro je přímočaré (libovolnou kombinaci cest a smyček lze jednotně vybarvit trojbarevnými opakujícími se vzory, s mírnými úpravami pro uzavřené smyčky). O případu rozhodovali Corradi a Hainal [7] . Úplnou domněnku dokázali Hajnal a Semeredi [4] a nyní je známá jako Hajnal-Szemeredi teorém. Jejich původní důkaz byl dlouhý a komplikovaný. Jednodušší důkaz podali Kirsted a Kostochka [8] . Polynomiální časový algoritmus pro nalezení jednotného zbarvení s tímto počtem barev byl popsán Kierstedem a Kostochkou. Marcelo Midlarzovi a Endre Szemeredimu připisují odlišný, dříve vyvinutý, nepublikovaný polynomiální časový algoritmus. Kiersted a Kostochka také oznámili silnější verzi teorému, že jednotné k -zabarvení existuje, pokud se součet stupňů libovolných dvou sousedních vrcholů rovná nejvýše , ale důkaz nebyl nikdy publikován.

Meyer [6] ve formě Brooksovy věty o jednotném zbarvení předpokládal, že jakýkoli souvislý graf s maximálním stupněm má jednotné zbarvení s nebo méně barvami, s výjimkou úplných grafů a lichých cyklů. Silnější verze domněnky říká, že každý takový graf má jednotné zbarvení s přesně barvami, s další výjimkou úplného bipartitního grafu , ve kterém mají obě části stejný lichý počet vrcholů [1] .

Seymour [9] navrhl posílení Hajnal-Szemerediho věty, která zahrnuje i Diracovu větu, že husté grafy jsou hamiltonovské  - domníval se, že pokud má jakýkoli vrchol v grafu s n vrcholy alespoň sousedy, pak graf obsahuje jako podgraf graf vytvořený spojením vrcholů vzdálených nejvýše k kroků v n -cyklu. Případ k  = 1 je vlastní Diracův teorém. Hajnal-Szemerediho teorém lze touto hypotézou překonat aplikací hypotézy pro velké hodnoty k na doplněk grafu a použitím spojitých sekvencí vrcholů z n -cyklu jako barevných tříd . Seymourova domněnka byla prokázána pro grafy, kde n je dostatečně velké ve srovnání s k [10] . Důkaz používá některé hluboké prostředky, včetně samotné Hajnal-Szemerediho věty.

Dalším zobecněním Haynal-Szemerediho věty je Bollobash-Eldridge-Katlin hypotéza (nebo zkráceně BEC hypotéza) [11] . Uvádí, že pokud G 1 a G 2 jsou n -vertexové grafy s maximálním stupněm resp . a pokud , pak G 1 a G 2 mohou být sbaleny. To znamená, že G 1 a G 2 mohou být reprezentovány na stejné množině n vrcholů bez společných hran. Hajnal-Szemerediho teorém je speciální případ domněnky, ve které G 2 je spojení disjunktních klik . Catlin [12] poskytuje podobnou, ale pevnější podmínku, na které a za kterých je zaručena existence takového obalu.

Speciální případy grafů

U žádného stromu s maximálním stupněm nepřekračuje jednotné chromatické číslo

[6]

s nejhorším případem na hvězdě. Většina stromů má však mnohem menší jednotné chromatické číslo - pokud má strom s n vrcholy , pak má jednotné zbarvení pouze se třemi barvami [13] . Furmanchik [1] studoval jednotný chromatický počet součinů grafů .

Výpočetní složitost

Studoval se také problém nalezení jednotného zbarvení s co nejmenším počtem barev (pod hranicí Hainal-Semeredi). Přímou redukci z vybarvení grafu na jednotné zabarvení lze dokázat přidáním dostatečného množství izolovaných vrcholů do grafu, což ukazuje, že testování, zda má graf jednotné zabarvení s daným počtem barev (větším než dvě), je NP-úplné . Problém se však stává zajímavějším, když je omezen na speciální třídu grafů nebo z hlediska parametrizované složitosti . Bodlander a Fomin [14] ukázali, že daný graf G a počet barev c , lze ověřit, zda G může být rovnoměrně c -barevné v čase O( n O( t ) ), kde t  je šířka stromu G . Zejména rovnoměrné zbarvení lze optimálně vyřešit v polynomiálním čase pro stromy (jak je známo díky Chenovi a Lee [15] ) a vnějších rovinných grafů . Existuje také polynomiální časový algoritmus pro jednotné vybarvování rozdělených grafů [16] . Fellowes, Fomin, Lokshtanov et al [17] však dokázali, že když je šířka stromu parametrem algoritmu, problém je W[1]-těžký. Je tedy nepravděpodobné, že existuje polynomiální časový algoritmus, který je nezávislý na tomto parametru, nebo dokonce, že závislost na parametru může být ohraničena exponentem ve vzorci doby běhu.

Aplikace

Jeden z důvodů pro zvažování jednotného zbarvení navrhl Meyer [6] v souvislosti s problémy s plánováním . V této aplikaci představují vrcholy grafu sadu úkolů, které je třeba provést, a hrany spojují dva úkoly, které nelze provést současně. Zbarvení tohoto grafu představuje rozdělení úkolů do podmnožin, které lze provádět současně. Potom počet barev ve zbarvení odpovídá počtu kroků potřebných k úplnému dokončení úkolu. Podle konvencí vyvažování zátěže je žádoucí provádět stejný nebo téměř stejný počet úkolů v každém kroku a toto vyvažování je přesně to, co dává jednotné zbarvení. Furmanchik [1] zmínil specifickou aplikaci tohoto typu problému rozvrhování, a to rozdělení univerzitních kurzů podle akademických hodin tak, aby byly kurzy rovnoměrně rozloženy do dostupných časových úseků, aby se zabránilo přiřazení nekompatibilních párů kurzů ke stejnému času.

Hajnal-Szemerediho teorém byl také použit k omezení rozptylu součtů náhodných veličin s omezenou závislostí [18] [19] . Pokud (jako v případě místního Lovasova lemmatu ) každá proměnná závisí na většině ostatních, lze použít jednotné obarvení grafu závislostí k rozdělení proměnných do nezávislých podmnožin, v nichž lze vypočítat Chernoffovy meze , což poskytne lepší hranice pro rozptyl, než kdyby byly rozděleny nejednotným způsobem.

Poznámky

  1. ↑ 1 2 3 4 Furmańczyk, 2006 .
  2. ↑ Všimněte si, že když je k větší než počet vrcholů v grafu, existuje vždy jednotné zbarvení s k barvami, ve kterých všechny barevné třídy mají nula nebo jeden vrchol na třídu, takže každý graf má jednotný chromatický práh.
  3. ↑ 12. Erdős , 1964 .
  4. ↑ 1 2 Hajnal, Szemerédi, 1970 .
  5. ↑ Kierstead, Kostochka, Mydlarz, Szemerédi, 2010 , str. 217–224.
  6. ↑ 1 2 3 4 Meyer, 1973 .
  7. ↑ Corrádi, Hajnal, 1963 .
  8. ↑ Kierstead, Kostochka, 2008 .
  9. ↑ Seymour, 1974 .
  10. ↑ Komlós, Sárközy, Szemerédi, 1998 .
  11. ↑ Bollobás, Eldridge, 1978 .
  12. ↑ Catlin, 1974 .
  13. ↑ Bollobás, Guy, 1983 .
  14. ↑ Bodlaender, Fomin, 2005 .
  15. ↑ Chen, Lih, 1994 .
  16. ↑ Chen, Ko, Lih, 1996 .
  17. ↑ Fellows, Fomin, Lokshtanov, 2007 .
  18. ↑ Pemmaraju, 2001 .
  19. ↑ Janson, Ruciński, 2002 .

Literatura

Odkazy