Csillagszínezés
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)

Gráfok színezése