T-zbarvení - T-coloring

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

v teorie grafů, a T-zbarvení grafu , vzhledem k soubor T nezáporných celých čísel obsahujících 0, je funkce který mapuje každý vrchol na kladné celé číslo (barva ) takové, že pokud u a w pak sousedí .[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, 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 je definován pro každý vrchol proti z G podle

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

Vztah k chromatickému číslu

Tvrzení. .[3]

Důkaz. Každý T-barvení G je také vrcholové zbarvení G, tak Předpokládejme to a Vzhledem k tomu, společný vrchol k- funkce barvení pomocí barev Definujeme tak jako

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

tak Proto d je T-barvení G. Od té doby d používá k barvy, Tudíž,

T-rozpětí

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

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

[4]

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

  • Pro každého k-chromatický graf G s klikou velikosti a každá konečná množina T nezáporných celých čísel obsahujících 0,
  • 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, [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, [5]

Viz také

Reference

  1. ^ A b Chartrand, Gary; Zhang, Ping (2009). "14. Barvení, vzdálenost a nadvláda". Teorie chromatického grafu. CRC Press. 397–402.
  2. ^ W. K. Hale, Přiřazení frekvence: Teorie a aplikace. Proc. IEEE 68 (1980) 1497–1514.
  3. ^ M. B. Cozzens a F. S. Roberts, T-zbarvení grafů a problém s přiřazením kanálu. Congr. Číslo. 35 (1982) 191–208.
  4. ^ Chartrand, Gary; Zhang, Ping (2009). "14. Barvení, vzdálenost a nadvláda". Teorie chromatického grafu. CRC Press. str. 399.
  5. ^ A b M. B. Cozzens a F. S. Roberts, T-zbarvení grafů a problém s přiřazením kanálu. Congr. Číslo. 35 (1982) 191–208.