完全三部份圖的全著色

Abstract

一個圖型G 的全著色可視為一種映射Ⅱ：V （G ）UE（G）－－＞｛１，２…｝ 使得 （１）任意相鄰的兩點或相鄰的兩邊都對應到不同的數字；（２）任意的點跟邊相鄰 都對應到不同的數字，一個圖型G 的全著色數X （G ）是指最小的數K 使得G 的某一 個全著色的對應數字集合為｛１，２，…K ｝，從X （G ）的定義中，很明顯地X （ Ｇ）＞＝△（Ｇ）＋１。 關於O 的全著色，已經分別被Bermond ，陳和傳證明出當t ＝２或t 是偶數並且ｒ 是奇數則o 是屬於第二型，其它情況則O 是屬於第一型。在這篇論文中，我們所 要探討的是完全三部份圖的全著色，特別是在非平衡的完全三部份圖，我們將證明所 有的非平衡完全三部份圖都是第一型。