T-раскраска

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

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

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

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

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

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

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

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

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

${\displaystyle d(v)=(r+1)c(v)}$.

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

${\displaystyle \left|d(u)-d(w)\right|=\left|(r+1)c(u)-(r+1)c(w)\right|}$

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

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

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

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

T-размах

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

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

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

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

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