T-раскраска графа , заданная множеством T неотрицательных целых, содержащим 0, — это функция , которая отображает каждую вершину графа G в положительное целое (цвет) так, что [1]. Простыми словами, абсолютное значение разности между двумя цветами смежных вершин должно не принадлежать фиксированному множеству T. Концепцию предложил Уильям К. Хейл[2]. Если T = {0}, это сводится к обычной раскраске вершин.

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

Дополняющая раскраска T-раскраски c, которая обозначается как , определяется для каждой вершины v графа G как

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

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

править

T-хроматическое число   — это число цветов, которые могут быть использованы для T-раскраски графа G. T-хроматическое число равно хроматическому числу,  [3].

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

править

Любая T-раскраска графа G является также раскраской вершин графа G, такая, что  . Предположим, что   и  .

Если дана функция k-раскраски вершин   с в цвета 1, 2,..,k.

Мы определим   как

 .

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

 
 ,

так что  .

Таким образом, d является T-раскраской графа G. Поскольку d использует k цветов,  .

Следовательно,  

T-размах

править

Для T-раскраски c графа G, c-размах   по всем   V(G).

T-размах   графа G — это   всех раскрасок c графа G[4]

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

Для любой k-раскраски графа G с кликой размера   и любого конечного множества T неотрицательных целых чисел, содержащего 0,  .

Для любого графа G и любого конечного множества T неотрицательных целых чисел, содержащего 0, наибольшим элементом которого является r,  ,  [5].
Для любого графа G и любого конечного множеств T неотрицательных целых чисел, содержащего 0, мощность которого равна t,  .  [5].

Примечания

править
  1. 1 2 Chartrand, Zhang, 2009, с. 397–402.
  2. Hale, 1980, с. 1497–1514.
  3. Cozzens, Roberts, 1982, с. 191–208.
  4. Chartrand, Zhang, 2009, с. 399.
  5. 1 2 Cozzens, Roberts, 1982, с. 191–208.

Литература

править
  • Gary Chartrand, Ping Zhang. 14. Colorings, Distance, and Domination // Chromatic Graph Theory. — CRC Press, 2009.
  • Hale W. K. Frequency assignment: Theory and applications // Proc. IEEE. — 1980. — Т. 68.
  • Cozzens M. B., Roberts F. S. T -colorings of graphs and the Channel Assignment Problem // Congr. Numer.. — 1982. — Вып. 35.