Acyklické zbarvení - Acyclic coloring

Acyklický chromatický počet McGeeův graf je 3.

v teorie grafů, an acyklické zbarvení je (správné) zbarvení vrcholů ve kterém každý 2-chromatické podgraf je acyklický. The acyklické chromatické číslo A(G) grafu G je nejméně barev potřebných pro jakékoli acyklické zbarvení G.

Acyklické zbarvení je často spojováno s grafy vloženými na nerovinné povrchy.

Horní hranice

A(G) ≤ 2 právě tehdy G je acyklický.

Hranice na A (G) ve smyslu Δ (G), maximální stupeň z G, zahrnout následující:

Milníkem ve studiu acyklického zbarvení je následující kladná odpověď na domněnku o Grünbaumovi:

Teorém (Borodin 1979 ) A (G) ≤ 5 pokud G je rovinný graf.

Grünbaum (1973) představil acyklické zbarvení a acyklické chromatické číslo a předpokládal výsledek ve výše uvedené větě. Borodinův důkaz zahrnoval několik let pečlivé kontroly 450 redukovatelných konfigurací. Jedním z důsledků této věty je, že každý rovinný graf lze rozložit na nezávislá sada a dva indukovaný lesy. (Stein1970, 1971 )

Algoritmy a složitost

to je NP-kompletní zjistit, zda A (G) ≤ 3. (Kostochka 1978 )

Coleman & Cai (1986) ukázal, že rozhodovací varianta problému je NP-úplná, i když G je bipartitní graf.

Gebremedhin et al. (2008) prokázal, že každé správné zbarvení vrcholů a chordální graf je také acyklické zbarvení. Protože chordální grafy mohou být optimálně vybarveny v O (n + m) času, totéž platí pro acyklické zbarvení této třídy grafů.

Algoritmus lineárního času pro acyklické vybarvení grafu maximálního stupně ≤ 3 pomocí 4 barev nebo méně byl dán Skulrattanakulchai (2004).

Viz také

Reference

  • Borodin, O. V. (1979), „O acyklickém zbarvení planárních grafů“, Diskrétní matematika, 25 (3): 211–236, doi:10.1016 / 0012-365X (79) 90077-3.
  • Burstein, M. I. (1979), „Každý čtyřmocný graf má acyklické 5-zbarvení (v ruštině)“, Soobšč. Akad. Nauk Gruzin. SSR, 93: 21–24.
  • Grünbaum, B. (1973), „Acyklické zbarvení planárních grafů“, Israel J. Math., 14 (4): 390–408, doi:10.1007 / BF02764716.
  • Coleman, Thomas F .; Cai, Jin-Yi (1986), „Problém cyklického zbarvení a odhad řídkých pytlovinských matic“ (PDF), SIAM Journal o algebraických a diskrétních metodách, 7 (2): 221–235, doi:10.1137/0607026.
  • Fertin, Guillaume; Raspaud, André (2008), „Acyklické vybarvení grafů maximálního stupně pět: stačí devět barev“, Dopisy o zpracování informací, 105 (2): 65–72, CiteSeerX  10.1.1.78.5369, doi:10.1016 / j.ipl.2007.08.022.
  • Gebremedhin, Assefaw H .; Tarafdar, Arijit; Pothen, Alex; Walther, Andrea (2008), „Efektivní výpočet řídkých hesiánů pomocí barvení a automatické diferenciace“, INFORMS Journal o práci na počítači, 21 (2): 209–223, doi:10.1287 / ijoc.1080.0286.
  • Jensen, Tommy R .; Toft, Bjarne (1995), Problémy s barvením grafů, New York: Wiley-Interscience, ISBN  978-0-471-02865-9.
  • Kostochka, A. V. (1978), Horní hranice chromatických funkcí grafů, Doktorská práce (v ruštině), Novosibirsk.
  • Kostochka, Alexandr V .; Stocker, Christopher (2011), "Grafy s maximálním stupněm 5 jsou acyklicky 7barevné", Ars Mathematica Contemporanea, 4 (1): 153–164, doi:10.26493/1855-3974.198.541, PAN  2785823.
  • Skulrattanakulchai, San (2004), „Acyklické barvení subkubických grafů“, Dopisy o zpracování informací, 92 (4): 161–167, doi:10.1016 / j.ipl.2004.08.002.
  • Stein, S. K. (1970), "B-sady a problémy s barvením", Býk. Amer. Matematika. Soc., 76 (4): 805–806, doi:10.1090 / S0002-9904-1970-12559-9.
  • Stein, S. K. (1971), „B-množiny a rovinné mapy“, Pacific J. Math., 37 (1): 217–224, doi:10.2140 / pjm.1971.37.217.
  • Varagani, satish; Venkaiah, V. Ch .; Yadav, Kishore; Kothapalli, Kishore (2009), „Acyklické vrcholové zbarvení grafů maximálního stupně šest“, LAGOS'09 - Páté latinskoamerické algoritmy, grafy a optimalizační sympozium, Elektronické poznámky v diskrétní matematice, 35, Elsevier, s. 177–182, doi:10.1016 / j.endm.2009.11.030, PAN  2579427

externí odkazy