T-värjäys

Graafin T-väritys , jonka antaa ei-negatiivisten kokonaislukujen joukko T , joka sisältää 0:n, on funktio , joka kuvaa G:n jokaisen kärjen positiiviseksi kokonaisluvuksi ( väri ) siten, että [1] . Yksinkertaisesti sanottuna vierekkäisten kärkien kahden värin välisen eron itseisarvo ei saa kuulua kiinteään joukkoon T . Konseptin ehdotti William K. Hale [2] . Jos T = {0} , tämä tiivistyy normaaliin kärkiväritykseen. $G=(V,E)$ $c:V(G)\rightarrow \mathbb {N}$ $(u,w)\in E(G)\Rightarrow \left|c(u)-c(w)\right|\notin T$

T -värityksen c komplementaarinen väritys , jota merkitään , määritellään graafin G as kullekin kärjelle v , missä s on suurin määrä värejä, jotka funktion c [1] graafin G kärki on osoittanut. . ${\overline {c))$
${\overline {c}}(v)=s+1-c(v)$

T -kromaattinen luku

T-kromaattinen luku on värien määrä, jolla voidaan T - värjätä graafi G . T -kromaattinen luku on yhtä suuri kuin kromaattinen luku, [3] . ${\näyttötyyli \chi _{T}(G)}$ ${\näyttötyyli \chi _{T}(G)=\chi (G)}$

Todiste

Mikä tahansa G :n T -värjäys on myös G :n huippuvärjäys siten, että . Oletetaan, että ja . $\chi _{T}(G)\geqslant \chi (G)$ ${\näyttötyyli \chi (G)=k}$ $r=max(T)$

Annettu k-väritysfunktio pisteiden kanssa väreihin 1, 2,..,k. $c:V(G)\rightarrow \mathbb {N}$

Me määrittelemme kuinka $d:V(G)\rightarrow \mathbb {N}$

d(v)=(r+1)c(v)

Kaikille kahdelle vierekkäiselle graafin G pisteelle u ja w

\left|d(u)-d(w)\right|=\left|(r+1)c(u)-(r+1)c(w)\oikea|

=(r+1)\left|c(u)-c(w)\right|\geqslant r+1

niin . $\left|d(u)-d(w)\right|\notin T$

Siten d on G :n T -väritys . Koska d käyttää k väriä, . $\chi _{T}(G)\leqslant k=\chi (G)$

Siksi ■ ${\näyttötyyli \chi _{T}(G)=\chi (G)}$

T -span

Graafin G T - väritykselle c c on alueen V(G) yli . ${\displaystyle sp_{T}(c)=\max\{|c(u)-c(w)|\))$ $uw\in$

Kuvaajan G T -väli on kaikki graafin G värit c [4] $sp_{T}(G)$ $\min\{sp_{T}(c)\}$

Joitakin T-välin rajoja on annettu alla:

Kaikille k-värityksille graafille G, jolla on koon klikki ja mikä tahansa ei-negatiivisten kokonaislukujen äärellinen joukko T, joka sisältää 0, . $\omega$ $sp_{T}(K_{\omega })\leqslant sp_{T}(G)\leqslant sp_{T}(K_{k})$

Jokaiselle graafille G ja mille tahansa ei-negatiivisten kokonaislukujen äärelliselle joukolle T, joka sisältää 0:n ja jonka suurin alkio on r , , [5] . Jokaiselle graafille G ja mille tahansa ei-negatiivisten kokonaislukujen äärelliselle joukolle T, joka sisältää 0:n kardinaalisuudesta t, . [5] . $sp_{T}(G)\leqslant (\chi (G)-1)(r+1)$ ${\näyttötyyli \chi _{T}(G)=\chi (G)}$
$sp_{T}(G)\leqslant (\chi (G)-1)t$ ${\näyttötyyli \chi _{T}(G)=\chi (G)}$

Muistiinpanot

↑ 1 2 Chartrand, Zhang, 2009 , s. 397–402.
↑ Hale, 1980 , s. 1497-1514
↑ Cozzens ja Roberts 1982 , s. 191-208.
↑ Chartrand, Zhang, 2009 , s. 399.
↑ 1 2 Cozzens ja Roberts, 1982 , s. 191-208.

Kirjallisuus

Gary Chartrand, Ping Zhang. 14. Väritykset, etäisyys ja dominointi // Kromaattinen graafiteoria. - CRC Press, 2009.
Hale WK Taajuustehtävä: Teoria ja sovellukset // Proc. IEEE. - 1980. - T. 68.
Cozzens MB, Roberts FS T -kaavioiden väritykset ja kanavan osoitusongelma // Congr. Numero.. - 1982. - Numero. 35 .