論Halin圖的均勻著色

On the Equitable Coloring of Halin Graphs

洪碧霞(Pi-Hsia Hung)

指導教授 ： 李國偉

國立臺灣大學/理學院/數學研究所/碩士(2005年)

https://doi.org/10.6342/NTU.2005.01813

摘要

Halin圖 是一個在平面上由內部點度數大於2的樹及連接樹的葉子的圈所組成的平面圖,我們將Halin圖用 來表示. 如果圖上的點可以用 個顏色來著色使得相鄰的點著不同的顏色且顏色類的大小差最多是1,我們就說這個圖是可均勻著色. 令 表圖上的點的最大度數,陳伯亮等人,提出以下這個猜測: 如果一個連通圖 不是 ,這三類的話,則 可以用 個顏色來均勻著色. 在這篇論文中我們要證明任意的Halin圖,除了 ,皆可以用 個顏色來均勻著色.

關鍵字

均勻著色

並列摘要

A Halin graph is a planar graph consisting of a tree with no vertex of degree two and a cycly connecting the leaves of the tree. We write . A graph is said to be equitably -colorable if the vertices of is colored with colors such that there are no two adjacent vertices of the same color and the size of the color classes differ by at most one. Let be the maximum degree of a vertex in graph . Chen et al. conjectured that a connected graph is equitable -colorable if is not a complete graph , or an odd cycle , or a complete bipartite graph for all . In this thesis, we prove that any Halin graph except has an equitable -coloring.

並列關鍵字

equitable coloring

參考文獻

[1] W. Meyer, Equitable coloring, Amer. Math. Monthly, 80 (1973) 920-922.

[2] A. C. Tucker, Perfect graphs and an application to optimizing municipal

services, SIAM Rev., 15 (1973) 585-590.

[3] A. Hajnal and E. Szemer_edi, Proof of a conjecture of Erd}os, in: A. R_enyi

and V. T. S_os (eds.), Combinatorial Theory and Its Applications, Vol. II,