| dbo:abstract
|
- 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é, . 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 kiszámítható . Bármely rögzített r egészre polinom időben eldönthető, hogy adott intervallumgráf vagy részkromatikus száma legfeljebb r-e . (hu)
- 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é, . 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 kiszámítható . Bármely rögzített r egészre polinom időben eldönthető, hogy adott intervallumgráf vagy részkromatikus száma legfeljebb r-e . (hu)
|
