Т-раскраска - T-coloring

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

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

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

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

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

куда s - наибольший цвет, присвоенный вершине грамм посредством c функция.^[1]

Связь с хроматическим числом

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

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

${ Displaystyle д (v) = (г + 1) с (v)}$

Для каждых двух соседних вершин ты и ш из грамм,

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

так ${ Displaystyle | d (и) -d (ш) | notin T.}$ Следовательно d это Т-крашивание грамм. С d использует k цвета, ${ Displaystyle чи _ {T} (G) Leq к = чи (G).}$ Как следствие, ${ Displaystyle чи _ {T} (G) = чи (G).}$

Т-охватывать

Пролет Т-крашивание c из грамм определяется как

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

В Т-охватывать определяется как:

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

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

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

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

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

Смотрите также

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

Рекомендации