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 vezette be.
Csillagkromatikus szám 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 alapján minden minorra zárt gráfosztályon korlátos. Ezt az eredményt 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:
A fentiből következik, hogy ha G síkgráf, akkor
A fentiből következik, hogy ha G síkgráf, akkor
A fentiből szintén következik, hogy ha a G síkgráf girthparamétere g, akkor:
Ha G síkgráf, akkor
Ha G síkgráf, akkor
Ha a G gráf favastagsága legfeljebb k, akkor
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 megmutatták, hogy az optimális csillagszínezés megtalálása NP-teljes még akkor is, ha G páros gráf.
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.
Jegyzetek
. . . . . .
További információk Star colorings and acyclic colorings (1973), present at the Research Experiences for Graduate Students (REGS) at the University of Illinois, 2008. André Raspaud: Star Coloring of Graphs (2009)
Kategória:Gráfok színezése