Т-розфарбування

Два T-розфарбування графа для T = {0, 1, 4}

T-розфарбування графа $G=(V,E)$, задане множиною T невід'ємних цілих, що містить 0, — це функція $c:V(G)\rightarrow \mathbb {N}$, яка відображає кожну вершину графа G у додатне ціле (колір) так, що $(u,w)\in E(G)\Rightarrow \left|c(u)-c(w)\right|\notin T$. Простими словами, абсолютне значення різниці між двома кольорами суміжних вершин повинно не належати фіксованій множині T. Концепцію запропонував Вільям К. Гейл. Якщо T = {0}, це зводиться до звичайного розфарбування вершин.

Додаткове розфарбування T-розфарбування c, яке позначається як ${\overline {c}}$, визначається для кожної вершини v графа G як${\overline {c}}(v)=s+1-c(v)$де s — найбільший номер кольору, призначений вершині графа G функцією c.

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

T-хроматичне число $\chi _{T}(G)$ — це число кольорів, які можуть бути використані для T-розфарбування графа G. T-хроматичне число дорівнює хроматичному числу$\chi _{T}(G)=\chi (G)$.

Доведення

Будь-яке T-розфарбування графа G є також розфарбуванням вершин графа G, так що $\chi _{T}(G)\geqslant \chi (G)$. Припустимо, що $\chi (G)=k$ і $r=max(T)$.

Якщо дана функція k-розфарбування вершин $c:V(G)\rightarrow \mathbb {N}$ с у кольори 1, 2,..,k.

Ми визначимо $d:V(G)\rightarrow \mathbb {N}$ як:

$d(v)=(r+1)c(v)$.

Для будь-яких двох суміжних вершин u і w графа G

$\left|d(u)-d(w)\right|=\left|(r+1)c(u)-(r+1)c(w)\right|$

$=(r+1)\left|c(u)-c(w)\right|\geqslant r+1$,

так що $\left|d(u)-d(w)\right|\notin T$.

Таким чином, d є T-розфарбуванням графа G. Оскільки d використовує k кольорів, $\chi _{T}(G)\leqslant k=\chi (G)$.

Отже, $\chi _{T}(G)=\chi (G)$ ■

T-розмах

Для T-розфарбування c графа G, c-розмах $sp_{T}(c)=\max\{|c(u)-c(w)|\}$ по всім $uw\in$ V(G).

T-розмах $sp_{T}(G)$ графа G — це $\min\{sp_{T}(c)\}$ усіх розфарбовувань c графа G

Деякі межі T-розмаху наведені нижче: Для будь-якого k-розфарбування графа G з клікою розміру $\omega$ і будь-якою скінченною множиною T невід'ємних цілих чисел, що містить 0, $sp_{T}(K_{\omega })\leqslant sp_{T}(G)\leqslant sp_{T}(K_{k})$.

Для будь-якого графа G і будь-якої скінченної множини T невід'ємних цілих чисел, що містить 0, найбільшим елементом якого є r, $sp_{T}(G)\leqslant (\chi (G)-1)(r+1)$, $\chi _{T}(G)=\chi (G)$.

Для будь-якого графа G і будь-якої скінченної множини T невід'ємних цілих чисел, що містить 0, потужність якої дорівнює t, $sp_{T}(G)\leqslant (\chi (G)-1)t$. $\chi _{T}(G)=\chi (G)$.

Література

• 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.