Т-окраска

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

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

Дополнительная раскраска T -раскраски c , обозначаемая как, определяется для каждой вершины v графа G как${\displaystyle {\overline {c}}}$

${\displaystyle {\overline {c}}(v)=s+1-c(v)}$

где s — наибольший цвет, назначенный вершине G функцией c . ^[1]

Предложение. . ^[3]${\displaystyle \chi _{T}(G)=\chi (G)}$

Доказательство. Каждая T -раскраска графа G также является вершинной раскраской графа G , поэтому Предположим, что и Дана общая функция вершинной k -раскраски с использованием цветов Мы определяем как${\ displaystyle \ chi _ {T} (G) \ geq \ chi (G).}$${\displaystyle \chi(G)=k}$${\displaystyle r=\max(T).}$${\displaystyle c:V(G)\to \mathbb {N} }$${\displaystyle \{1,\ldots ,k\}.}$${\displaystyle d:V(G)\to \mathbb {N} }$

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

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

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

поэтому d является T -раскраской графа G. Поскольку d использует k цветов, следовательно ,${\displaystyle |d(u)-d(w)|\notin T.}$${\displaystyle \chi _{T}(G)\leq k=\chi (G).}$${\displaystyle \chi _{T}(G)=\chi (G).}$

Диапазон T -раскраски c графа G определяется как

${\displaystyle sp_{T}(c)=\max _{u,w\in V(G)}|c(u)-c(w)|.}$

Пролет T определяется как :

${\displaystyle sp_{T}(G)=\min _{c}sp_{T}(c).}$^[4]

Некоторые границы T -пролета приведены ниже:

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

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

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

• Раскраска графа