A matematika, azon belül a gráfelmélet területén egy gráf összegszínezése (sum coloring) a gráf csúcsainak pozitív egész számokkal való címkézése oly módon, hogy a szomszédos csúcsokhoz tartozó címkék nem egyezhetnek meg, a címkék összege pedig minimális legyen. Ezt a minimális összeg a gráf kromatikus összege (chromatic sum). A kromatikus összeg és az összegszínezés bevezetése gráfelméleten kívül eső terminológiával Supowit nevéhez fűződik (1987), gráfelméleti eszközökkel elsőként (Supowittől függetlenül) Ewa Kubicka vizsgálta ezeket a fogalmakat 1989-es doktori disszertációjában.
A kromatikus összeghez szükséges címkék száma meghaladhatja a gráf kromatikus számát, és még ha a kromatikus szám korlátos, az optimális kromatikus összeg eléréséhez szükséges különböző címkék száma tetszőlegesen nagy lehet.
A kromatikus összeg meghatározása NP-nehéz. Fák és pszeudoerdők esetében azonban lineáris időben, külsíkgráfoknál pedig polinom időben meghatározható. Intervallumgráfokra és páros gráfokra létezik konstans tényezőjű közelítő algoritmus. Ettől még a Supowit eredeti, VLSI-tervezésről szóló cikkében, valamit ütemezési feladatokban szóba jövő intervallumgráf-eset NP-nehéz marad.
Az összegszínezés a csúcsokon kívül alkalmazható az élekre (összeg-élszínezés) valamint a csúcsok és élek uniójára (totális összegszínezés) is.
Fordítás
Jegyzetek
Kategória:Gráfok színezése