T-раскраска

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

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

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

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

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

Доказательство

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

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

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

$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|$

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

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

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

Следовательно, $\chi _{T}(G)=\chi (G)$ ■

T-размах

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

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

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

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

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