T着色

グラフ理論において、グラフのT彩色とは${\displaystyle G=(V,E)}$0 を含む非負整数の集合Tが与えられたとき、関数は${\displaystyle c:V(G)\to \mathbb {N} }$各頂点を正の整数（色）にマッピングし、uとwが隣接している場合は、${\displaystyle |c(u)-c(w)|\notin T}$^{[ 1 ]}簡単に言うと、隣接する頂点の 2 つの色の差の絶対値は、固定集合Tに属していてはならない。この概念は、ウィリアム K. ヘイルによって導入された。^{[ 2 ]} T = {0}の場合、共通頂点彩色に帰着する。

T-クロマチック数、${\displaystyle \chi _{T}(G),}$は、 GのT彩色で使用できる最小の色数です。

T彩色cの補色は、${\displaystyle {\overline {c}}}$Gの各頂点vに対して、次のように定義される。

${\displaystyle {\overline {c}}(v)=s+1-c(v)}$

ここで、sはc関数によってGの頂点に割り当てられた最大の色である。^{[ 1 ]}

命題。$\displaystyle \chi _{T}(G)=\chi (G)}$[ ^{3 ]​}

証明。GのすべてのT彩色もGの頂点彩色なので、${\displaystyle \chi _{T}(G)\geq \chi (G).}$仮に${\displaystyle \chi (G)=k}$そして${\displaystyle r=\max(T).}$共通の頂点k彩色関数が与えられた場合${\displaystyle c:V(G)\to \mathbb {N} }$色を使って${\displaystyle \{1,\ldots ,k\}.}$定義${\displaystyle d:V(G)\to \mathbb {N} }$として

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

Gの任意の隣接する 2 つの頂点uとwに対して、

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

それで${\displaystyle |d(u)-d(w)|\notin T.}$したがって、dはGのT彩色である。dはk色を使用するので、$\displaystyle \chi _{T}(G)\leq k=\chi (G).$その結果、$\displaystyle \chi _{T}(G)=\chi (G).$

GのT彩色cのスパンは次のように定義されます。

${\displaystyle sp_{T}(c)=\max _{u,w\in V(G)}|c(u)-c(w)|.}$

Tスパンは次のように定義されます。

${\displaystyle sp_{T}(G)=\min _{c}sp_{T}(c).}$^{[ 4 ]}

Tスパンのいくつかの範囲を以下に示します。

• サイズがクリークである任意のk彩色グラフGに対して${\displaystyle \omega }$0 を含む非負整数の有限集合Tはすべて、${\displaystyle sp_{T}(K_{\omega })\leq sp_{T}(G)\leq sp_{T}(K_{k}).}$
• グラフGと、最大要素がrである 0 を含む非負整数の有限集合Tについて、${\displaystyle sp_{T}(G)\leq (\chi (G)-1)(r+1).}$^{[ 5 ]}
• 任意のグラフGと、 0 を含む非負整数の任意の有限集合T （その濃度はtである）に対して、${\displaystyle sp_{T}(G)\leq (\chi (G)-1)t.}$^{[ 5 ]}

• グラフの彩色