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, . .
Примітки
Література