Hvězdné zbarvení - Star coloring

Hvězdný chromatický počet Dyckův graf je 4, zatímco chromatické číslo je 2.

v graf-teoretický matematika, a hvězdné zbarvení grafu G je (správné) zbarvení vrcholů ve kterém každý cesta na čtyřech vrcholech používá alespoň tři odlišné barvy. Ekvivalentně, v barvení hvězd, indukované podgrafy tvořené vrcholy libovolných dvou barev připojené komponenty to jsou hvězdné grafy. Hvězdné zbarvení zavedlo Grünbaum (1973).v hvězdné chromatické číslo z G je nejméně barev potřebných k označení barvy hvězd G.

Jedním zobecněním zbarvení hvězd je úzce související koncept acyklické zbarvení, kde je požadováno, aby každý cyklus používal alespoň tři barvy, takže dvoubarevné indukované podgrafy jsou lesy. Pokud označíme acyklické chromatické číslo grafu G podle , máme to , a ve skutečnosti každé hvězdné zbarvení G je acyklické zbarvení.

Bylo prokázáno, že hvězdné chromatické číslo je ohraničeno na každé správné menší uzavřené třídě pomocí Nešetřil & Ossona de Mendez (2003). Tyto výsledky dále zobecnil Nešetřil & Ossona de Mendez (2006) na všechna zbarvení s nízkou hloubkou stromů (standardní zbarvení a vybarvení hvězd je zbarvení s nízkou hloubkou stromů s příslušným parametrem 1 a 2).

Složitost

Ukázalo se to Albertson a kol. (2004) že je to NP-kompletní zjistit, zda , i když G je graf, který je obojí rovinný a bipartitní.Coleman & Moré (1984) ukázal, že nalezení optimálního zbarvení hvězd je NP-tvrdé i když G je bipartitní graf.

Reference

  • Albertson, Michael O .; Chappell, Glenn G .; Kierstead, Hal A .; Kündgen, André; Ramamurthi, Radhika (2004), "Barvení bez dvoubarevného P4„“, Electronic Journal of Combinatorics, 11 (1), PAN  2056078.
  • Coleman, Thomas F .; Moré, Jorge (1984), „Odhad řídkých hesenských matic a problémy s barvením grafů“ (PDF), Matematické programování, 28 (3): 243–270, doi:10.1007 / BF02612334, PAN  0736293.
  • Fertin, Guillaume; Raspaud, André; Reed, Bruce (2004), „Hvězdné vybarvení grafů“, Journal of Graph Theory, 47 (3): 163–182, doi:10.1002 / jgt.20029, PAN  2089462.
  • Grünbaum, Branko (1973), „Acyklické zbarvení planárních grafů“, Israel Journal of Mathematics, 14: 390–408, doi:10.1007 / BF02764716, PAN  0317982.
  • Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2003), „Barvení a homomorfismy menších uzavřených tříd“, Diskrétní a výpočetní geometrie: Goodman-Pollack FestschriftAlgoritmy a kombinatorika, 25, Springer-Verlag, str. 651–664, PAN  2038495.
  • Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2006), „Hloubka stromu, hranice zbarvení podgrafu a homomorfismus“, European Journal of Combinatorics, 27 (6): 1022–1041, doi:10.1016 / j.ejc.2005.01.010, PAN  2226435.

externí odkazy