A matematika, azon belül a gráfelmélet területén egy G gráf csillagszínezése (star coloring) olyan csúcsszínezés, amiben bármely négy csúcson átmenő út legalább 3 különböző színt tartalmaz. Ezzel egyenértékű megfogalmazásban, a csillagszínezésben bármely két szín által meghatározott feszített részgráfok összefüggő komponensei csillaggráfok. A csillagszínezést (Grünbaum 1973) vezette be.

A Dyck-gráf csillagkromatikus száma 4, míg kromatikus száma 2.

Csillagkromatikus szám

szerkesztés

A   csillagkromatikus szám a G csillagszínezéséhez szükséges legkevesebb szín száma.

A csillagszínezés egyik általánosítása az aciklikus (körmentes) színezés; itt minden körnek legalább három színt kell használnia, ezért a két szín által meghatározott feszített részgráfok erdők. Ha a G gráf aciklikus kromatikus számát  -vel jelöljük,  , és valójában minden csillagszínezés egyben aciklikus színezés is.

A csillagkromatikus szám (Nešetřil & Ossona de Mendez 2003) alapján minden minorra zárt gráfosztályon korlátos. Ezt az eredményt (Nešetřil & Ossona de Mendez 2006) tovább általánosította az összes alacsony fa-mélységű színezésre (a normál színezés és a csillagszínezés olyan alacsony fa-mélységű színezésnek tekinthető, melyek megfelelő paramétere 1, illetve 2).

További eredmények:

 [1]

A fentiből következik, hogy ha G síkgráf, akkor  [1]

 [2]

A fentiből következik, hogy ha G síkgráf, akkor  [2]

A fentiből szintén következik, hogy ha a G síkgráf girthparamétere g, akkor:

 [2]

Ha G síkgráf, akkor  [3]

Ha G síkgráf, akkor  [2]

Ha a G gráf favastagsága legfeljebb k, akkor  [4]

Ennek következménye: ha G külsíkgráf, akkor   és ez az eredmény éles.

Sejtés: létezik olyan G síkgráf, melyre  

Számítási bonyolultság

szerkesztés

(Coleman & Moré 1984) megmutatták, hogy az optimális csillagszínezés megtalálása NP-teljes még akkor is, ha G páros gráf.

(Albertson et al. 2004) megmutatták, hogy annak eldöntése, hogy   NP-teljes, még akkor is, ha G-ről ismert, hogy síkgráf és páros.

További információk

szerkesztés