T-раскраска

T-раскраска графа $G=(V,E)$$G=(V,E)$, заданная множеством T неотрицательных целых, содержащим 0, — это функция $c:V(G)\to <!--\; \to \; -->\mathbb{N}$$c:V(G)\rightarrow \mathbb {N}$, которая отображает каждую вершину графа G в положительное целое (цвет) так, что $(u,w)\in <!--\; \in \; -->E(G)\Rightarrow <!--\; \Rightarrow \; -->\left|c(u)-<!--\; -\; -->c(w)\right|\notin <!--\; \notin \; -->T$$(u,w)\in E(G)\Rightarrow \left|c(u)-c(w)\right|\notin T$. Простыми словами, абсолютное значение разности между двумя цветами смежных вершин должно не принадлежать фиксированному множеству T. Концепцию предложил Уильям К. Хейл. Если T = {0}, это сводится к обычной раскраске вершин.

Две T-раскраски графа для T = {0, 1, 4}

Дополняющая раскраска T-раскраски c, которая обозначается как $\stackrel{¯<!--\; ¯\; -->}{c}$${\overline {c}}$, определяется для каждой вершины v графа G как
$\stackrel{¯<!--\; ¯\; -->}{c}(v)=s+1-<!--\; -\; -->c(v)$${\overline {c}}(v)=s+1-c(v)$
, где s — наибольший номер цвета, назначенные вершине графа G функцией c.

T-хроматическое числоПравить

T-хроматическое число ${\mathrm{\chi <!--\; \chi \; -->}}_T(G)$$\chi _{T}(G)$  — это число цветов, которые могут быть использованы для T-раскраски графа G. T-хроматическое число равно хроматическому числу, ${\mathrm{\chi <!--\; \chi \; -->}}_T(G)=\mathrm{\chi <!--\; \chi \; -->}(G)$$\chi _{T}(G)=\chi (G)$ .

ДоказательствоПравить

Любая T-раскраска графа G является также раскраской вершин графа G, такая, что ${\mathrm{\chi <!--\; \chi \; -->}}_T(G)⩾<!--\; ⩾\; -->\mathrm{\chi <!--\; \chi \; -->}(G)$$\chi _{T}(G)\geqslant \chi (G)$ . Предположим, что $\mathrm{\chi <!--\; \chi \; -->}(G)=k$$\chi (G)=k$  и $r=max(T)$$r=max(T)$ .

Если дана функция k-раскраски вершин $c:V(G)\to <!--\; \to \; -->\mathbb{N}$$c:V(G)\rightarrow \mathbb {N}$  с в цвета 1, 2,..,k.

Мы определим $d:V(G)\to <!--\; \to \; -->\mathbb{N}$$d:V(G)\rightarrow \mathbb {N}$  как

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

Для любых двух смежных вершин u и w графа G

$\left|d(u)-<!--\; -\; -->d(w)\right|=\left|(r+1)c(u)-<!--\; -\; -->(r+1)c(w)\right|$$\left|d(u)-d(w)\right|=\left|(r+1)c(u)-(r+1)c(w)\right|$ 

$=(r+1)\left|c(u)-<!--\; -\; -->c(w)\right|⩾<!--\; ⩾\; -->r+1$$=(r+1)\left|c(u)-c(w)\right|\geqslant r+1$ ,

так что $\left|d(u)-<!--\; -\; -->d(w)\right|\notin <!--\; \notin \; -->T$$\left|d(u)-d(w)\right|\notin T$ .

Таким образом, d является T-раскраской графа G. Поскольку d использует k цветов, ${\mathrm{\chi <!--\; \chi \; -->}}_T(G)⩽<!--\; ⩽\; -->k=\mathrm{\chi <!--\; \chi \; -->}(G)$$\chi _{T}(G)\leqslant k=\chi (G)$ .

Следовательно, ${\mathrm{\chi <!--\; \chi \; -->}}_T(G)=\mathrm{\chi <!--\; \chi \; -->}(G)$$\chi _{T}(G)=\chi (G)$  ■

T-размахПравить

Для T-раскраски c графа G, c-размах $s{p}_T(c)=max\{|c(u)-<!--\; -\; -->c(w)|\}$$sp_{T}(c)=\max\{|c(u)-c(w)|\}$  по всем $uw\in <!--\; \in \; -->$$uw\in$  V(G).

T-размах $s{p}_T(G)$$sp_{T}(G)$  графа G — это $min\{s{p}_T(c)\}$$\min\{sp_{T}(c)\}$  всех раскрасок c графа G

Некоторые границы T-размаха даны ниже:

Для любой k-раскраски графа G с кликой размера $\mathrm{\omega <!--\; \omega \; -->}$$\omega$  и любого конечного множества T неотрицательных целых чисел, содержащего 0, $s{p}_T(K_{\mathrm{\omega <!--\; \omega \; -->}})⩽<!--\; ⩽\; -->s{p}_T(G)⩽<!--\; ⩽\; -->s{p}_T(K_k)$$sp_{T}(K_{\omega })\leqslant sp_{T}(G)\leqslant sp_{T}(K_{k})$ .

Для любого графа G и любого конечного множества T неотрицательных целых чисел, содержащего 0, наибольшим элементом которого является r, $s{p}_T(G)⩽<!--\; ⩽\; -->(\mathrm{\chi <!--\; \chi \; -->}(G)-<!--\; -\; -->1)(r+1)$$sp_{T}(G)\leqslant (\chi (G)-1)(r+1)$ , ${\mathrm{\chi <!--\; \chi \; -->}}_T(G)=\mathrm{\chi <!--\; \chi \; -->}(G)$$\chi _{T}(G)=\chi (G)$ .
Для любого графа G и любого конечного множеств T неотрицательных целых чисел, содержащего 0, мощность которого равна t, $s{p}_T(G)⩽<!--\; ⩽\; -->(\mathrm{\chi <!--\; \chi \; -->}(G)-<!--\; -\; -->1)t$$sp_{T}(G)\leqslant (\chi (G)-1)t$ . ${\mathrm{\chi <!--\; \chi \; -->}}_T(G)=\mathrm{\chi <!--\; \chi \; -->}(G)$$\chi _{T}(G)=\chi (G)$ .