Teljes színezés

A Clebsch-gráf teljes színezése 8 színnel. Minden színpár legalább egy élen megjelenik. Több színnel nem lehetséges teljes színezés: bármely 9-színezésben lenne olyan szín, ami csak egy csúcson jelenik meg, és nem lenne elég szomszédos csúcs a csúcson lévő színhez tartozó összes párosítás kimerítéséhez. Ezért a Clebsch-gráf akromatikus száma 8.

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.

Bonyolultságelmélet

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 $G=(V,E)$ gráf és a $k$ pozitív egész

KÉRDÉS: létezik-e $V$-nek $k$ vagy több diszjunkt $V_1,V_2,\dots ,V_k$ halmazokra való particionálása úgy, hogy minden $V_i$ a $G$-nek egy független csúcshalmaza és egyik $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.

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.

Algoritmusok

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

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

Speciális gráfosztályok

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, a páros gráfok komplementerei (tehát a két csúcsnál nagyobb független halmazzal nem rendelkező gráfok), a kográfok és az intervallumgráfok, és még a fák is.

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

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

Fordítás

• Sablon:Fordítás

További információk

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