Komplementer színezés

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.

Komplementer színezés három színnel (bal felső ábra): a gráf jól színezése 3 színnel nem lehetséges. A kék részgráf klikket alkot (jobb alsó ábra), míg piros és zöld részgráfok a komplementer gráfban alkotnak klikkeket (jobbra fent, illetve balra lent).

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.

Fordítás

• Ez a szócikk részben vagy egészben a Cocoloring című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

• .
• .
• .
• .
• .
• .

• Matematikaportál • összefoglaló, színes tartalomajánló lap