- 作者: 陳伯亮;傅恆霖;王俊昌
- 作者服務機構: 國立交通大學應用數學研究所
- 中文摘要: 一個圖的全著色是將點和邊都著色,使得相鄰的點,相鄰的邊及相鄰的點和邊都具有不同的?色。一個圖能全著色所需要的最少顏色數?該圖的全著色數。 本文利用特殊的拉丁方陣來求得兩類圖的全著色數;分??平衡的完全t部份圖及點數?2n,及秩數?2n-3的規則圖。
- 英文摘要: A total coloring π of a graph G is a mapping π V(G)∪E(G) → {l,2,...} such that (1) no two adjacent vertices or edges have the same image; and (2) the image of each vertex is distinct from the images of its incident edges. The total chromatic number χt(G) of a graph G is thd smallest integer k such that G has a total coloring having image set {1,,2,...,k } . From the definition of χt(G), it is clear that χt(G) In this paper, we apply some special latin squares to classify the total colorings of two classes of graphs. First, we show that the balanced complete t-partite graph, Ort, is of type two, if and only if t = 2 or t is even and r is odd. Secondly, we prove that a (2n-3)-regular graph G of order 2n is of type one, if and only if the complement of G, Gc, is a disjoint union of two 1-factors.
- 中文關鍵字: total coloring; total chromatic number
- 英文關鍵字: --