T-раскраска

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

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

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

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

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

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

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

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

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

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

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

$|d(u)-d(w)|=|(r+1)c(u)-(r+1)c(w)|$

$=(r+1)|c(u)-c(w)|⩾r+1$,

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

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

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

T-размах

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

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

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

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

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

Литература

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Статья