T-zbarvení - T-coloring

Dvě T-barvy v grafu pro T = {0, 1, 4}

v teorie grafů, a T-zbarvení grafu ${ displaystyle G = (V, E)}$, vzhledem k soubor T nezáporných celých čísel obsahujících 0, je funkce ${ displaystyle c: V (G) až mathbb {N}}$ který mapuje každý vrchol na kladné celé číslo (barva ) takové, že pokud u a w pak sousedí ${ displaystyle | c (u) -c (w) | notin T}$.^[1] Jednoduše řečeno, absolutní hodnota rozdílu mezi dvěma barvami sousedních vrcholů nesmí patřit do pevné množiny T. Koncept představil William K. Hale.^[2] Li T = {0} redukuje se na běžné zbarvení vrcholů.

The T-chromatické číslo, ${ displaystyle chi _ {T} (G),}$ je minimální počet barev, které lze použít v a T-barvení G.

The doplňkové zbarvení z T-zbarvení C, označeno ${ displaystyle { overline {c}}}$ je definován pro každý vrchol proti z G podle

${ displaystyle { overline {c}} (v) = s + 1-c (v)}$

kde s je největší barva přiřazená k vrcholu G podle C funkce.^[1]

Vztah k chromatickému číslu

Tvrzení. ${ displaystyle chi _ {T} (G) = chi (G)}$.^[3]

Důkaz. Každý T-barvení G je také vrcholové zbarvení G, tak ${ displaystyle chi _ {T} (G) geq chi (G).}$ Předpokládejme to ${ displaystyle chi (G) = k}$ a ${ displaystyle r = max (T).}$ Vzhledem k tomu, společný vrchol k- funkce barvení ${ displaystyle c: V (G) až mathbb {N}}$ pomocí barev ${ displaystyle {1, ldots, k }.}$ Definujeme ${ displaystyle d: V (G) až mathbb {N}}$ tak jako

${ displaystyle d (v) = (r + 1) c (v)}$

Pro každé dva sousední vrcholy u a w z G,

${ Displaystyle | d (u) -d (w) | = | (r + 1) c (u) - (r + 1) c (w) | = (r + 1) | c (u) -c ( w) | geq r + 1}$

tak ${ displaystyle | d (u) -d (w) | notin T.}$ Proto d je T-barvení G. Od té doby d používá k barvy, ${ displaystyle chi _ {T} (G) leq k = chi (G).}$ Tudíž, ${ displaystyle chi _ {T} (G) = chi (G).}$

T-rozpětí

Rozpětí a T-zbarvení C z G je definován jako

${ displaystyle sp_ {T} (c) = max _ {u, w v V (G)} | c (u) -c (w) |.}$

The T-rozpětí je definován jako:

${ displaystyle sp_ {T} (G) = min _ {c} sp_ {T} (c).}$^[4]

Některé hranice T-span jsou uvedeny níže:

• Pro každého k-chromatický graf G s klikou velikosti ${ displaystyle omega}$ a každá konečná množina T nezáporných celých čísel obsahujících 0, ${ displaystyle sp_ {T} (K _ { omega}) leq sp_ {T} (G) leq sp_ {T} (K_ {k}).}$

• Pro každý graf G a každá konečná množina T nezáporných celých čísel obsahujících 0, jejichž největší prvek je r, ${ displaystyle sp_ {T} (G) leq ( chi (G) -1) (r + 1).}$^[5]

• Pro každý graf G a každá konečná množina T nezáporných celých čísel obsahujících 0, jejichž mohutnost je t, ${ displaystyle sp_ {T} (G) leq ( chi (G) -1) t.}$ ^[5]

Viz také

• Barvení grafu

Reference