T-раскраска графа , заданная множеством T неотрицательных целых, содержащим 0, — это функция , которая отображает каждую вершину графа G в положительное целое (цвет) так, что . Простыми словами, абсолютное значение разности между двумя цветами смежных вершин должно не принадлежать фиксированному множеству T. Концепцию предложил Уильям К. Хейл. Если T = {0}, это сводится к обычной раскраске вершин.
Дополняющая раскраска T-раскраски c, которая обозначается как , определяется для каждой вершины v графа G как , где s — наибольший номер цвета, назначенные вершине графа G функцией c.
T-хроматическое число T-хроматическое число — это число цветов, которые могут быть использованы для T-раскраски графа G. T-хроматическое число равно хроматическому числу, .
Доказательство Любая 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
Некоторые границы T-размаха даны ниже:
Для любой k-раскраски графа G с кликой размера и любого конечного множества T неотрицательных целых чисел, содержащего 0, .
Для любого графа G и любого конечного множества T неотрицательных целых чисел, содержащего 0, наибольшим элементом которого является r, , . Для любого графа G и любого конечного множеств T неотрицательных целых чисел, содержащего 0, мощность которого равна t, . .
Примечания
Литература
Категория:Раскраска графа