T-zbarvení - T-coloring

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:
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
- ^ A b Chartrand, Gary; Zhang, Ping (2009). "14. Barvení, vzdálenost a nadvláda". Teorie chromatického grafu. CRC Press. 397–402.
- ^ W. K. Hale, Přiřazení frekvence: Teorie a aplikace. Proc. IEEE 68 (1980) 1497–1514.
- ^ 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.
- ^ Chartrand, Gary; Zhang, Ping (2009). "14. Barvení, vzdálenost a nadvláda". Teorie chromatického grafu. CRC Press. str. 399.
- ^ 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.