From Wikipedia, the free encyclopedia
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 (Lesniak & Straight 1977) tanulmányozta és nevezte el. (Jørgensen 1995) adja meg a kritikus 3-komplementer kromatikus gráfok jellemzését, míg (Fomin, Kratsch & Novelli 2002) a gráfok komplementer kromatikus számát közelítő algoritmusokat ír le. (Zverovich 2000) 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.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
