高秩圖的全著色

Abstract

一個圖G 的全著色是一種映射π：V （G ）∪E （G ）→｛１，２，…｝使得（１） （１）任二個相鄰的點和相鄰的邊都不會對應到相同的數字，（２）任一點與其接觸 的邊都不會對應到相同的數字。一個圖G 的全著色數X （G ）是指一個最小的數K 使 得G 有一種全著色π：V （G ）∪E （G ）→｛１，２，…｝由這個定義，我們可以 知道X （G ）＞△（G ）＋１。 在這篇論文中是針對有２n 個點，最大秩為２n －３的圖來研究。主要是證明了一個 有２n 個點，秩為２n －３的規則圖G 為第一型，也就是說，全著色數X （G ）＝△ （G ）＋１若且唯若此圖的補圖是二組不相交的完全配對。 Behzad和Vizing分別在１９６５及１９６４年做了以下的猜測： 全著色猜測：對任意圖，其全著色數小於或等於其最大秩加一。 如果這個猜測是正確的，我們就可以令全著色數為最大秩加一的圖為第一型：其全著 色數為最大秩加二的圖為第二型。Hilton曾經對點數２n 而最大秩為２n －２的圖解 出其為第一型或第二型的充要條件。在這篇論文中，我所針對的是有２n 個點，最大 秩為２n －１的圖來做研究。主要是做出（２n －３）規則圖的部份。即此規則圖為 第一型若且唯若此圖的補圖是二組不相交的完全配對。