臺灣博碩士論文加值系統

給定任意一個圖形，我們說此圖形具備有一個k種顏色的均勻著色指的是對此圖形裡的所有頂點我們可以找到一種特別的塗色方式，而其特別處在於我們只須使用k種顏色就可以使得圖形中任意的相鄰兩頂點塗上不同顏色，以及每一種顏色所塗色的頂點總數滿足兩兩之間差距至多為一。
在1970年，Hajnal 和 Szemerédi這兩位學者證明了只要使用的顏色數比此圖形的最大度數還要多，則此圖形就必定可以用這麼多個顏色來均勻著色。所以只要我們使用的顏色數比最大度數多，就可以均勻著色。那接下來我們想知道的是如果剛好使用的顏色數是最大度數，是否還是可以均勻著色。而Yen這位學者在1997年提出對於最大度數大於著色數的圖形可用最大度數個顏色均勻著色的必要條件。並且這個結果Yen這位學者已經證明在二部圖和三著色四正則的圖形時不只必要條件成立，充分條件也是成立的。
本篇論文的主要目標則是想探討k-正則三部圖可以用k個顏色來均勻著色的充分必要條件是什麼。首先我們證明了對一個給定的圖形，只要此圖形的最大度數比著色數和總點數的一半還大，則此圖形可以用最大度數個顏色均勻著色的充要條件是這個圖形不是K2n+1,2n+1。接著我們證明了只要一個圖形的最大度數等於3，此圖形就可以用3個顏色均勻著色的充份必要條件。最後我們還有一些結果，證明了k-正則三部圖在k比5來的大而且這個圖形又滿足某些條件時，也可以恰好使用k個顏色來均勻著色。

Abstract(Chinese) i
Abstract(English) ii
Acknowledgements iv
Contents v
List of Figures vi
1 Introduction 1
1.1 Graphs . . . . . . . . . . . . . . . . . . . 1
1.2 Different Kinds of Graphs . . . . . . . . . . 3
1.3 Vertex Coloring . . . . . . . . . . . . . . . 4
2 Well-known Results 6
2.1 Connected Graphs . . . . .. . . . . . . . . . 6
2.2 General Graphs . . . . . . . . . . . . . . . 9
3 A Graph G with Δ(G)>= max{χ(G),|V(G)|/2} 12
4 k-regular and 3-chromatic Graphs 14
4.1 A Graph G with 3>=Δ(G)>=χ(G) . . . . . . ...15
4.2 5-regular and 3-chromatic Graphs . . . . . . 19
4.3 k-regular and 3-chromatic Graphs . . . . . . 27
5 Conclusions 31
References 32

[1] B. Bollob´as and R.-K. Guy, Equitable and proportional coloring of trees, J. Combin. Theory Ser. B 34(1983), 177-186.
[2] J.-A. Bondy and U. S. R. Murty, Graph theory with applications, Macmillan, London, 1976.
[3] R. L. Brooks, On colouring the nodes of a network, Proc. Cambridge Philos. Soc. 37(1941), 194-197.
[4] F.-H. Chang, B.-L. Chen and C.-H. Yen, Equitable Δ-Coloring of Graphs, manuscript.
[5] G.-J. Chang, A note on equitable colorings of forests, European Journal of Combinatorics Vol. 30(2009), 809-812.
[6] B.-L. Chen and K.-W. Lih, Equitable coloring of trees, J. Combin. Theory Ser. B 61(1994), 83-87.
[7] B.-L. Chen, K.-W. Lih and P.-L. Wu, Equitable coloring and the maximun degree, Europ. J. Combinatorics 15(1994), 443-447.
[8] B.-L. Chen, M.-T. Ko and K.-W. Lih, Equitable and m-bounded coloring of split graphs, LNCS 1120(1995), 1-5.
[9] B.-L. Chen, K.-W. Lih and J.-H. Yan, Equitable coloring of interval graphs and products of graphs, manuscript, 1998.
[10] B.-L. Chen, K.-C. Huang and C.-H. Yen, Chromatic coloring with a maximum color class, Discrete Math. 308(2008), 5533-5537.
[11] H. Furma´nczyk and M. Kubale, The complexity of equitable vertex coloring of graphs, Journal of Applied Computer Science Vol. 13(2005) No. 2, 95-107.
[12] R.-K. Guy, Monthly resesrch problems, 1969-1975, Amer. Math. Monthly 82(1975), 995-1004.
[13] A. Hajnal and E. Szemer´edi, Proof of a conjecture of Erd¨os, in: Combinatorial Theory and Its Applications, Vol. II, P. Erd¨os, A. R´enyi, and V. T. S´os (eds),
Colloq. Math. Soc. J´anos Bolyai, Vol. 4, North Holland, Amsterdam (1970), 601-623.
[14] K.-W. Lih, The equitable coloring of graphs, Handbook of combinatorial Optimization, D.-Z. Du and P.M. Pardalos (Eds.), Kluwer Academic Publishers, Vol. 3(1998) 543-566.
[15] K.-W. Lih and P.-L. Wu, On equitable coloring of bipartite graphs, Discrete Math. 151(1996), 155-160.
[16] C.-Y. Lin, The equitable coloring of the bipartite graphs, Master D. Thesis, Tunghai University, 1995.
[17] W. Meyer, Equitable coloring, Amer. Math. Monthly, 80(1973), 920-922.
[18] Weifan Wang and Kemin Zhang, Equitable colorings of line graphs and complete r-partite graphs, Systems Science and Mathematical Sciences Vol.13(2000) No.2.
[19] Douglas B. West, Introduction to graph theory, Second Edition, Prentice-Hall, Inc., Upper Saddle River, NJ 07458, 2001.
[20] C.-H. Wu, On the equitable-coloring of the complete t-partite graphs, Master D. Thesis, Tunghai University, 1994.
[21] H.-P. Yap and Y. Zhang, On equitable colorings of graphs, manuscript, 1996.
[22] H.-P. Yap and Y. Zhang, The equitable Δ-coloring conjecture holds for outerplanar graphs, Bulletin of the Inst. of Math. Academia Sinica 25(1997), 143-149.
[23] H.-P. Yap and Y. Zhang, Equitable colorings of planar graphs, J. Combin. Math. Combin. Comput. 27(1998), 97-105.
[24] C.-H. Yen, Equitable coloring of 3-partite graphs, Master D. Thesis, Tunghai University, Taiwan, 1997.