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álypá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 gráf és a pozitív egész KÉRDÉS: létezik-e -nek vagy több diszjunkt halmazokra való particionálása úgy, hogy minden a -nek egy független csúcshalmaza és egyik 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. A1.1: GT5, pg.191.
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 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 -nel arányos, de az arány konstans tagja precízen nem ismert..
Fordítás
Jegyzetek
További információk A compendium of NP optimization problems A Bibliography of Harmonious Colourings and Achromatic Number by Keith Edwards
Kategória:Gráfok színezése