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

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

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

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

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

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

Доведення

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

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

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

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

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

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

$=(r+1)|c(u)-c(w)|⩾r+1$,

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

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

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

T-розмах

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

T-розмах $s{p}_T(G)$ графа G — це $\min \{s{p}_T(c)\}$ усіх розфарбовувань c графа GШаблон:Sfn

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

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

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

Література

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Стаття