李德財臺灣大學：資訊工程學研究所魏廷恩Wei, Tin-EnTin-EnWei2007-11-262018-07-052007-11-262018-07-052006http://ntur.lib.ntu.edu.tw//handle/246246/54134Vizing的定理敘述一個簡單圖 $G$ 能使用 $Delta (G)+1$ 顏色做邊著色，$Delta (G)$ 為圖 $G$ 的度數。這立即引進了分類的問題─假如最少著色數 $chi '(G)=Delta (G)$，$G$ 為 class one;否則 $G$ 為 class two。本論文延伸了Vizing的定理，介紹一個新的想法，假如我們要對 $G$的一個邊做著色且這個邊在 $k$ 顏色下滿足未飽合條件，$k leq Delta (G)$，則這個邊可使用 $k$ 個顏色中的一個顏色做著色。在任意的著色順序下，一個簡單圖 $G$ 的每一邊皆能在 $Delta (G)+1$ 顏色下滿足未飽合條件。假如我們能找到 $G$ 的某一邊著色順序，使得每一個被著色的邊可以在 $Delta (G)$ 顏色下滿足未飽合條件，則 $G$ 為 class one。假如一個簡單圖 $G$ 所有 $Delta (G)$ 的點形成的誘導子圖是一個樹林或仙人掌，仙人掌的末端區塊必須為一個邊，則我們能找到這樣的一個著色順序，證明 $G$ 為 class one.同樣的我們也能在 reduced proper interval graph 找到這樣的一個著色順序。Vizing's Theorem states that a simple graph $G$ can be edge-colored with $Delta (G)+1$ colors, where $Delta (G)$ is the degree of the graph $G$. This immediately introduces the classification problem -- if chromatic index $chi '(G)=Delta (G)$, then $G$ is in class one; otherwise $G$ is in class two. We extend the proof of Vizing's Theorem to introduce a new idea that if we want to color an edge of $G$ and this edge satisfies an unsaturated condition under $k$ colors, for some $k leq Delta (G)$, then this edge can be colored with one of $k$ colors. Thus, for any coloring order, each edge of a simple graph $G$ satisfies the unsaturated condition under $Delta (G)+1$ colors. If we find a feasible edge-coloring order of $G$ such that each edge can satisfy the unsaturated condition under $Delta (G)$ colors, then $G$ is in class one. We show that if the subgraph induced by all $Delta (G)$-vertices is a forest or a cactus in which each end block is an edge, then $G$ has such a feasible coloring order and $G$ is in class one. We also find such a feasible coloring order for reduced proper interval graphs.1 Introduction 5 2 Edge-coloring of the unsaturated condition 7 3 Reduced proper interval graph 13 4 Conclusion 18 5 Appendix 19 References 31816201 bytesapplication/pdfen-US邊著色edge coloringthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/54134/1/ntu-95-R93922058-1.pdf