| dbo:abstract
|
- A matematika, azon belül a gráfelmélet területén egy G gráf komplementer színezése, esetleg koszínezése (cocoloring) alatt a csúcsok olyan színezését értjük, melynél minden színosztály vagy G-ben, vagy G komplementerében alkot független csúcshalmazt. Ezzel egyenértékű megfogalmazás szerint G csúcsainak olyan színezése, ahol a színosztályok vagy klikket, vagy független csúcshalmazt feszítenek ki. A G gráf z(G) komplementer kromatikus száma (cochromatic number) a G komplementer színezéséhez szükséges legkevesebb színek száma. A 2 komplementer kromatikus számú gráfok éppen a páros gráfok, a páros gráfok komplementerei és a split gráfok. Mivel a követelmény, hogy minden színosztály klikk vagy független csúcshalmaz legyen, gyengébb a jó színezésnél megkívántnál (ahol minden színosztály független csúcshalmaz) és erősebb mint a részszínezés esetében (ahol minden színosztálynak klikkek diszjunkt uniójának kell lennie), ezért G komplementer kromatikus száma kisebb vagy egyenlő G kromatikus számánál, de nagyobb vagy egyenlő G részkromatikus számánál. A komplementer színezést elsőként tanulmányozta és nevezte el. adja meg a kritikus 3-komplementer kromatikus gráfok jellemzését, míg a gráfok komplementer kromatikus számát közelítő algoritmusokat ír le. definiál egy „perfekt komplementer kromatikus gráfok” nevű gráfosztályt (annak analógiájára, ahogy a perfekt gráfokat definiálják a jó színezés segítségével), és megadja ezen gráfok tiltott gráfok szerinti osztályozását. (hu)
- A matematika, azon belül a gráfelmélet területén egy G gráf komplementer színezése, esetleg koszínezése (cocoloring) alatt a csúcsok olyan színezését értjük, melynél minden színosztály vagy G-ben, vagy G komplementerében alkot független csúcshalmazt. Ezzel egyenértékű megfogalmazás szerint G csúcsainak olyan színezése, ahol a színosztályok vagy klikket, vagy független csúcshalmazt feszítenek ki. A G gráf z(G) komplementer kromatikus száma (cochromatic number) a G komplementer színezéséhez szükséges legkevesebb színek száma. A 2 komplementer kromatikus számú gráfok éppen a páros gráfok, a páros gráfok komplementerei és a split gráfok. Mivel a követelmény, hogy minden színosztály klikk vagy független csúcshalmaz legyen, gyengébb a jó színezésnél megkívántnál (ahol minden színosztály független csúcshalmaz) és erősebb mint a részszínezés esetében (ahol minden színosztálynak klikkek diszjunkt uniójának kell lennie), ezért G komplementer kromatikus száma kisebb vagy egyenlő G kromatikus számánál, de nagyobb vagy egyenlő G részkromatikus számánál. A komplementer színezést elsőként tanulmányozta és nevezte el. adja meg a kritikus 3-komplementer kromatikus gráfok jellemzését, míg a gráfok komplementer kromatikus számát közelítő algoritmusokat ír le. definiál egy „perfekt komplementer kromatikus gráfok” nevű gráfosztályt (annak analógiájára, ahogy a perfekt gráfokat definiálják a jó színezés segítségével), és megadja ezen gráfok tiltott gráfok szerinti osztályozását. (hu)
|
