A matematika, azon belül a gráfelmélet területén egy gráf részszínezése (subcoloring) a gráf csúcsaihoz színek rendelése oly módon, hogy minden színosztály klikkek diszjunkt unióját feszítse ki a gráfban – tehát minden színosztály egy-egy klasztergráfot alkosson.
A G gráfhoz tartozó χS(G) részkromatikus szám (subchromatic number) a G részszínezéséhez minimálisan szükséges színek száma. A részszínezést és a részkromatikus számot vezette be.
Egy gráf minden jó színezése és komplementer színezése egyben részszínezés is, így egy gráf részkromatikus száma legfeljebb a komplementer kromatikus számmal egyezik meg, ami viszont legfeljebb a kromatikus számmal.
A részszínezési probléma pontosan olyan nehéz, mint a színezésé, NP-nehéz. Annak megállapítása, hogy egy síkbarajzolható gráf részkromatikus száma legfeljebb 2-e, még akkor is NP-teljes, ha a szóban forgó gráf: háromszögmentes, maximális fokszáma 4 , összehasonlíthatósági gráf, 4 maximális fokszámmal , páros gráf élgráfja, 4 maximális fokszámmal , 5 girthparaméterű .
Egy kográf részkromatikus száma ellenben polinom időben kiszámítható . Bármely rögzített r egészre polinom időben eldönthető, hogy adott intervallumgráf vagy permutációgráf részkromatikus száma legfeljebb r-e .
Fordítás
Jegyzetek . . . . . . .
Kategória:Gráfok színezése