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

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$ [1]. Простими словами, абсолютне значення різниці між двома кольорами суміжних вершин повинно не належати фіксованій множині T. Концепцію запропонував Вільям К. Гейл[2]. Якщо T = {0}, це зводиться до звичайного розфарбування вершин.

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

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

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

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

Доведення

Будь-яке 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[4]

Деякі межі 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)$ [3].

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

Примітки

Chartrand, Zhang, 2009, с. 397–402.
Hale, 1980, с. 1497–1514.
Cozzens, Roberts, 1982, с. 191–208.
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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[FOOTNOTEChartrand,_Zhang2009397–402-1] Chartrand, Zhang, 2009, с. 397–402.

[FOOTNOTEHale19801497–1514-2] Hale, 1980, с. 1497–1514.

[FOOTNOTECozzens,_Roberts1982191–208-3] Cozzens, Roberts, 1982, с. 191–208.

[FOOTNOTEChartrand,_Zhang2009399-4] Chartrand, Zhang, 2009, с. 399.