|
T - 著色乃是由 Hale 於 1980 年為了解決幾個頻道分配問題而提出的一
套圖形理論系統。給定一個有限的非負整數集合 T，並以非負整數來對圖
形中的點進行著色。則相鄰兩點的顏色差距不可落入集合 T中，因此產生
了一個所謂的 T 著色。 1982 年，Cozzens 與 Roberts 證明了一個圖形
的最小 T -著色數介於兩個完全圖形的最小T -著色數中,所以我們把焦點
放在完全圖形的最小 T - 著色數上。Cozzens 與 Roberts 兩位學者曾經
證明當 T 是一個 r-initial set 時，對於任意圖形G，最小 T - 著色數
等於它的一般著色數的 (r+1) 倍。多位學者也曾經對於形如 T={0,
a,2,...,r,a,...b}(其中[a,b]包含一些(r+1)的倍數)，確定了完全圖形
的的最小 T - 著色數的值。由於這些探討僅限於一些特定的 a 和 b，所
以是否存在有一定的規則可以決定完全圖形的最小 T - 著色數，這個問
題引起了我們的興趣。我們以幾個點的顏色被決定之後，在 T 集合的限
制之下，不能再被使用的顏色令為不可取集。在這篇文章的前半部，我們
利用不可取集的觀念，以及數線化的表達作為工具，觀察不可取集在數線
上所顯現的規則性，了解被各個顏色所決定的不可取集彼此間的相對關係
，進一步推導出三種著色方法，並且確定在 (b-a) 小或等於 (r-1) 的條
件下完全圖形的最小 T -著色數。然而對於 (b-a) 大或等於 r 的情形，
僅僅能夠以例子加以說明。尚且無法給予一個確定的結果。在前半部的最
後，並對於 (b-a)大或等於 2r 的條件時，完全圖形的最小著色數，提出
一個猜想。連續 T - 著色本身仍是一個 T - 著色，另外加上所使用的顏
色，必須是連續的非負整數這個條件。然而並非每一種圖形皆有連續 T
著色。在這篇文章的後半部，我們只針對 (t-1)-path 圖形，分別討論
當 T 集合為r-ini-tial set 及 T={0,a,...,b} 時的連續 T - 著色。並
對於 T 為 r-initial set 的條件下，找到並證明連續 T 著色數的大小
。然而對於 T={0,a,...b}時的情況，僅僅能夠提出一種著色方法，為
(t-1)- path 的連續 T - 著色數提供一個上界。並且從方法中，察覺到
連續 T-著色的複雜性遠勝於一般的T - 著色。
|