(3.236.214.19) 您好!臺灣時間:2021/05/09 22:55
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

: 
twitterline
研究生:陳怡婷
研究生(外文):Yi-Ting Chen
論文名稱:k-正則三部圖之均勻著色
論文名稱(外文):Equitable Coloring of k-regular and 3-partite Graphs
指導教授:嚴志弘
指導教授(外文):Chih-Hung Yen
學位類別:碩士
校院名稱:國立嘉義大學
系所名稱:應用數學系研究所
學門:數學及統計學門
學類:數學學類
論文種類:學術論文
論文出版年:2009
畢業學年度:97
語文別:中文
中文關鍵詞:點著色著色數均勻著色均勻著色數最大度數正則圖二部圖多部圖
相關次數:
  • 被引用被引用:0
  • 點閱點閱:356
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:8
  • 收藏至我的研究室書目清單書目收藏:0
給定任意一個圖形,我們說此圖形具備有一個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.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔