Teljes színezés

A matematika, azon belül a gráfelmélet területén a teljes színezés (complete coloring) a harmonikus színezés ellentéte, abban az értelemben, hogy olyan jó csúcsszínezés, melyben minden színpár előfordul legalább egy szomszédos csúcspáron. A teljes színezés abban az értelemben minimális, hogy színosztály-párok összeolvasztásával nem alakítható át kevesebb színnel történő jó színezéssé. A G gráf akromatikus száma, ψ(G) a maximális színek száma, mellyel elvégezhető G teljes színezése.

A ψ(G) értékének megállapítása egy optimalizálási probléma. A teljes színezés döntési problémája a következőképpen mondható ki:

BEMENET: egy ${\displaystyle G=(V,E)}$ gráf és a ${\displaystyle k}$ pozitív egész

KÉRDÉS: létezik-e ${\displaystyle V}$-nek ${\displaystyle k}$ vagy több diszjunkt ${\displaystyle V_{1},V_{2},\ldots ,V_{k}}$ halmazokra való particionálása úgy, hogy minden ${\displaystyle V_{i}}$ a ${\displaystyle G}$-nek egy független csúcshalmaza és egyik ${\displaystyle V_{i},V_{j},V_{i}\cup V_{j}}$ halmazpár sem alkot független csúcshalmazt.

Az akromatikus szám meghatározása NP-nehéz; annak meghatározása, hogy adott számnál nagyobb-e, NP-teljes, ahogy azt Yannakakis és Gavril 1978-ban megmutatták a minimális értékű maximális párosítás problémájából való transzformációval.^[1]

Egy gráf minimális számú színnel való színezése mindenképpen teljes színezés, így egy teljes színezés színeinek minimalizálása csak a szokásos gráfszínezési probléma újrafogalmazása.

Rögzített k-ra lineáris időben megállapítható, hogy adott gráf akromatikus száma legalább k-e.^[2]

Az optimalizálási probléma lehetővé teszi a közelítést, és ${\displaystyle O\left(|V|/{\sqrt {\log |V|}}\right)}$ approximációs aránnyal közelíthető.^[3]

Az akromatikus szám problémájának NP-teljessége még néhány speciális gráfosztályra igaz, ezek közé tartoznak: a páros gráfok,^[2] a páros gráfok komplementerei (tehát a két csúcsnál nagyobb független halmazzal nem rendelkező gráfok),^[1] a kográfok és az intervallumgráfok,^[4] és még a fák is.^[5]

Fák komplementereinek akromatikus száma polinom időben kiszámítható.^[6] Fák esetében konstans faktorral approximálható.^[3]

Ismert, hogy az n dimenziós hiperkockagráf akromatikus száma ${\displaystyle {\sqrt {n2^{n}}}}$-nel arányos, de az arány konstans tagja precízen nem ismert.^[7]

• Ez a szócikk részben vagy egészben a Complete coloring 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.

• A compendium of NP optimization problems
• A Bibliography of Harmonious Colourings and Achromatic Number by Keith Edwards