完全點著色數及完全邊著色數

Abstract

完全點著色數，是指給圖之點著色，使得相鄰之點均著相異色，且任意二色均有相鄰 之二點著此二色時，所能使用顏色之最大數；而完全邊著色數，則給圖之邊著色，使 得相鄰之邊均著相異色，且任二色均有相鄰之二邊著此二色時，所能使用顏色之最大 數。本論文即在討論此二數。 本論文分四章。第一章作預備工作：介紹圖論及設計理論之一些概念；並依歷史、應 用及理論方面表達研究此一題目之動機。 第二章討論圖之完全點著色數。先提出完全點著色數之定義及基本性質；然後討論完 全點著色之插值定理；並決定一些特別圖之完全點著色數；最後我們討論圖之笛卡兒 乘積之完全點著色數。 第三章我們研究完全邊著色數。首先給完全邊著色數作一定義；然後討論完全圖及正 規部份圖之完全邊著色數的上限與完全邊著色之特性；由是得到無窮多之完全圖及正 規部份圖之完全邊著色數。 當我們研究完全點著色數及完全邊著色數的上限時，我們發現將該二數推廣為擬似完 全點著色數及擬似完全邊著色數，將更容易探討。於是在第四章中，我們討論此二新 數。我們先給此二數加以定義；並分別研究它們的上限；然後介紹有趣的Nordhaus- Gaddum定理；最後我們利用所得的上限，去決定一些圖的擬似完全點著色數及擬似完 全邊著色數。