Csillagszínezés

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

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 Sablon:Harvtxt vezette be.

Csillagkromatikus szám

A ${\chi }_s(G)$ 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 ${\chi }_a(G)$-vel jelöljük, ${\chi }_a(G)\le {\chi }_s(G)$, és valójában minden csillagszínezés egyben aciklikus színezés is.

A csillagkromatikus szám Sablon:Harvtxt alapján minden minorra zárt gráfosztályon korlátos. Ezt az eredményt Sablon:Harvtxt 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:

$\text{Ha }{\chi }_a(G)\le k,\text{ akkor }{\chi }_s(G)\le k\cdot 2^{k-1}$

A fentiből következik, hogy ha G síkgráf, akkor ${\chi }_s(G)\le 80$

${\chi }_s(G)\le {\chi }_a(G)(2{\chi }_a(G)-1)$

A fentiből következik, hogy ha G síkgráf, akkor ${\chi }_s(G)\le 45$

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

$\{\begin{array}{c}\text{ha }g\ge 7\text{, akkor }{\chi }_s(G)\le 9,\\ \text{ha }g\ge 5\text{, akkor }{\chi }_s(G)\le 16.\end{array}$

Ha G síkgráf, akkor ${\chi }_s(G)\le 30$

Ha G síkgráf, akkor ${\chi }_s(G)\le 20$

Ha a G gráf favastagsága legfeljebb k, akkor ${\chi }_s(G)\le k(k+3)/2+1$

Ennek következménye: ha G külsíkgráf, akkor ${\chi }_s(G)\le 6$ és ez az eredmény éles.

Sejtés: létezik olyan G síkgráf, melyre ${\chi }_s(G)=10$

Számítási bonyolultság

Sablon:Harvtxt megmutatták, hogy az optimális csillagszínezés megtalálása NP-teljes még akkor is, ha G páros gráf.

Sablon:Harvtxt megmutatták, hogy annak eldöntése, hogy ${\chi }_s(G)\le 3$ NP-teljes, még akkor is, ha G-ről ismert, hogy síkgráf és páros.

Jegyzetek

• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.

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)