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
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ábbkü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 illetve 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 present at the Research Experiences for Graduate Students ( REGS ) at the University of Illinois , André Raspaud : Star Coloring of Graphs Gráfok színezése