V teorii grafů je celkové zbarvení druhem zbarvení vrcholů a hran grafu. Pokud není výslovně uvedeno jinak, celkové zbarvení se považuje za správné v tom smyslu, že žádné sousední vrcholy a žádné sousední hrany a vrcholy ležící na koncích hran nejsou obarveny stejnou barvou.
Celkové chromatické číslo χ″( G ) grafu G je nejmenší počet barev potřebný pro celkové vybarvení G .
Celkový graf T = T( G ) grafu G je graf, ve kterém
S touto definicí se celkové zbarvení stane (správným) zbarvením vrcholu celkového grafu.
Několik vlastností χ″( G ):
Zde Δ( G ) je maximální mocnina a ch′( G ) je index předepsaného zbarvení hran .
Celkové zbarvení vzniká přirozeným způsobem, protože se jedná o jednoduchou směs zbarvení vrcholů a okrajů. Dalším krokem je uvažovat o horních hranicích celkového chromatického čísla v podmínkách maximálního stupně, analogicky s Brooksovými nebo Vizingovými teorémy . Ukázalo se, že určení horních hranic celkového zbarvení v závislosti na maximálním stupni je obtížný úkol a matematikům unikal 40 let.
Nejznámější odhad zní takto:
Dohad o celkovém zbarvení.
χ″( G ) ≤ Δ( G ) + 2.Výraz „totální zbarvení“ a formulaci domněnky zjevně nezávisle navrhli Behzad a Vizing v četných publikacích v letech 1964 až 1968 (podrobnosti viz kniha Jensena a Tofta [3] ).
Je známo, že tato domněnka platí pro několik důležitých tříd grafů, jako jsou bipartitní grafy a většina rovinných grafů , s výjimkou grafů s maximálním stupněm 6. Případ rovinných grafů bude vyřešen, pokud Vizingova domněnka rovinného grafu bude se ukázalo jako pravdivé. Také, pokud je dohad o předepsaném zbarvení hran pravdivý, pak χ″( G ) ≤ Δ( G ) + 3.
Byly získány některé výsledky týkající se celkového zbarvení. Například Kylakos a Read [4] dokázali, že zlomkový chromatický index celkového grafu pro graf G nepřesahuje Δ( G ) + 2.
Zmíníme také následující spojení mezi spojnicovým grafem a celkovým grafem :
T ( G ) je Euler právě tehdy , když L ( G ) je Euler .