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

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

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

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

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

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

Доведення

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

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

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

${\displaystyle d(v)=(r+1)c(v)}$.

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

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

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

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

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

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

T-розмах

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

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

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

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

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

Примітки

1. Chartrand, Zhang, 2009, с. 397–402.
2. Hale, 1980, с. 1497–1514.
3. Cozzens, Roberts, 1982, с. 191–208.
4. Chartrand, Zhang, 2009, с. 399.

Література

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