T-barvení

T-barvení grafu daného množinou T nezáporných celých čísel obsahujících 0 je funkce , která mapuje každý vrchol G na kladné celé číslo ( barva ) tak, že [1] . Zjednodušeně řečeno, absolutní hodnota rozdílu dvou barev sousedních vrcholů nesmí patřit do pevné množiny T . Koncept navrhl William K. Hale [2] . Pokud T = {0} , zmenší se to na normální zbarvení vrcholu.

Doplňkové zbarvení T -barvy c , které je označeno jako , je definováno pro každý vrchol v grafu G as , kde s je největší počet barev přiřazených vrcholu grafu G funkcí c [1] .

T -chromatické číslo

T-chromatické číslo je počet barev, které lze použít k T - barvení grafu G . T -chromatické číslo je rovno chromatickému číslu, [3] .

Důkaz

Jakékoli T -barvení G je také zbarvení vrcholu G tak, že . Předpokládejme, že a .

Je dána k-barvicí funkce vrcholů s do barev 1, 2,..,k.

Definujeme jak

.

Pro libovolné dva sousední vrcholy u a w grafu G

,

tak .

Tedy d je T -barvení G . Protože d používá k barev, .

Proto ■

T -span

Pro T -barvení c grafu G je c rozsah přes všechny V(G).

T -rozpětí grafu G je všechna zabarvení c grafu G [4]

Některé limity T-rozpětí jsou uvedeny níže:

Pro libovolné k-obarvení grafu G s klikou velikosti a libovolnou konečnou množinou T nezáporných celých čísel obsahujících 0, .

Pro libovolný graf G a libovolnou konečnou množinu T nezáporných celých čísel obsahujících 0, jejichž největší prvek je r , , [5] . Pro libovolný graf G a libovolnou konečnou množinu T nezáporných celých čísel obsahujících 0 mohutnosti t, . [5] .

Poznámky

  1. ↑ 1 2 Chartrand, Zhang, 2009 , str. 397–402.
  2. ↑ Hale, 1980 , str. 1497–1514
  3. ↑ Cozzens a Roberts 1982 , str. 191–208.
  4. ↑ Chartrand, Zhang, 2009 , s. 399.
  5. ↑ 1 2 Cozzens a Roberts, 1982 , s. 191–208.

Literatura