臺灣博碩士論文加值系統

論文名稱: 樹和毛毛蟲圖的對局著色數和對局色數 頁數: 27
校所組別: 國立中山大學應用數學所純數組
畢業時間及提要別: 八十七學年度第二學期碩士論文摘要
論文摘要:
在這篇論文, 我們考慮樹和毛毛蟲圖的對局著色數和對局色數. 樹的對局色數最大為四, 這是已經知道的, 而且存在著有對局色數為四的樹.
以下我們將要示出:
對於一個有對局色數為四的樹 (或是毛毛蟲圖) , 最少的頂點個數為十.
對於一個有對局著色數為四的樹 (或是毛毛蟲圖) , 最少的頂點個數為十四.
若T 是一個三- 正規的毛毛蟲圖而且T 的頂點數不小於一零二, 則T 的對局著色數為四.

In this thesis, we consider the game chromatic number and game coloring number for trees and caterpillars.
It is known that the game coloring number of a tree is at most 4 and there exist trees with game coloring number 4.
We show the following:
(1)10 is the minimum number of vertices for a tree (or caterpillar) with game coloring number 4.
(2)14 is the minimum number of vertices for a tree (or caterpillar) with game chromatic number 4.
(3)T is a 3-regular caterpillar and |V(T)| not less than 102, then $\chi_g(T) = 4$.

1. Introduction
1.1 Definition of Xg and colg
1.2 Trees and Caterpillars
1.3 Results of this thesis
2. Game chromatic number and game coloring number of trees
2.1 The bounds for trees
2.2 A minimum tree T with colg(T)=4
2.3 A minimum tree T with Xg(T)=4
3. Game chromatic number and game coloring number of cater-pillars
3.1 The bounds for caterpillars
3.2 Patterns,pre-patterns
3.3 Proof of Theorem 5

[1] H.L. Bodlaender, On the complexity of some coloring games, in: R.H. Mohring,editor, Graph Theoretic Concepts in computer Science,volume 484 of Leture Notes in Computer Science, 30-40, Springer-Verlag, 1991.
[2] T.Dinski and X.Zhu, An upper bound for the game chromatic of graphs, Discrete Mathematic, 11 (1998),590-602.
[3] P.Erdos and A.Hajnal, On chromatic number of graphs and set system, Acta. Math. Acad. Sci. Hungar. 17,61-19(1996).
[4] U.Faigle, U. Kern, H. Kierstead and W. T. Trotter, On the game chromatic number of some classes of graphs, Ars Combin. 35 (1993),143-150.
[5] D. Guan and X.Zhu, The game chromatic number of outerplanar graphs, Journal of Graph Theory, 30(1999),67-70.
[6] T. Jensen and B. Toft, Graph coloring Problems, John Wiley & Sons,1995.
[7] H.A. Kierstead and W.T. Trotter, Planar graph coloring With an uncooperative partner, J. Graph Theory 18 (1994), no. 6, 569-584.
[8] A.V. Kostochka, E. Sopena and X. Zhu, Acyclic chromatic number of graphs, J. Graph Theory 24 (1997), 331-340.
[9] C. St. J. A. Nash-William, Decomposition of finite graphs into forest, J. London Math. Soc. 39(1964).
[10] X. Zhu, The game coloring number of pseudo partial k-trees, Discrete Mathematic, to appear.
[11] X. Zhu, Game coloring number of planar graphs, Journal of Combinatorial Theory (B), 75(1999),245-258.
[12] X. Zhu, On the game coloring number of graphs, manuscript, 1998.
[13] Leizhen Cai and X.Zhu, The game chromatic index and game coloring index of graphs, 1998.