論Halin圖的均勻著色

Abstract

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.