請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/44992完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 張鎮華(Gerard Jennhwa Chang) | |
| dc.contributor.author | Wu-Hsiung Lin | en |
| dc.contributor.author | 林武雄 | zh_TW |
| dc.date.accessioned | 2021-06-15T04:00:38Z | - |
| dc.date.available | 2012-03-10 | |
| dc.date.copyright | 2010-03-10 | |
| dc.date.issued | 2010 | |
| dc.date.submitted | 2010-02-23 | |
| dc.identifier.citation | [1] B. Baker and E. Coffman, Mutual exclusion scheduling, Theoret. Comput. Sci. 162 (1996), No. 2, 225-243.
[2] D. Blum, D Torrey, R. Hammack, Equitable chromatic number of complete multipartite graphs, Missouri J. Math. Sci. 15 (2003), No. 2, 75-81. [3] B. Bollob'as and R.K. Guy, Equitable and proportional coloring of Trees, J. Combin. Theory Ser. B 34 (1983), No. 2, 177-186. [4] B.-L. Chen, M.-T. Ko and K.-W. Lih, Equitable and $m$-bounded coloring of split graphs, in: Combinatorics and Computer Science, Lecture Notes in Computer Science 1120 (M. Deza, R. Euler and I. Manoussakis, eds.), Springer, Berlin, 1996, pp. 1-5. [5] B.-L. Chen and K.-W. Lih, Equitable coloring of trees, J. Combin. Theory, Ser. B 61 (1994), No. 1, 83-87. [6] B.-L. Chen, K.-W. Lih and P.-L. Wu, Equitable coloring and the maximum degree, European J. Combin. 15 (1994), No. 5, 443-447. [7] B.-L. Chen, K.-W. Lih and J.-H. Yan, Equitable coloring of interval graphs and products of graphs, to appear in A Festschrift in honor of Professor Man Keung Siu, Hong Kong University Press, manuscript in 1998, to appear. [8] D. Duffus, B. Sands, R.E. Woodrow, On the chromatic number of the product of graphs, J. Graph Theory 9 (1985), No. 4, 487-495. [9] P. ErdH{o}s, Problem 9, in: Theory of Graphs and Its Applications (M. Fielder, Ed.), 159, Czech. Acad. Sci. Publ., Peague, 1964. [10] H. Furma'ncyzk, The complexity of equitable vertex coloring of graphs, J. Appl. Comput. Sci. 13 (2005), No. 2, 95-107. [11] H. Furma'ncyzk, Equitable colorings of graph products, Opuscula Math. 26 (2006), No. 1, 31-44. [12] R.K. Guy, Monthly research problems 1969-1975, Amer. Math. Monthly 82 (1975), No. 10, 995-1004. [13] A. Hajnal and E. Szemer'edi, Proof of a conjecture of P. ErdH{o}s, in: Combinatorial Theory and Applications (P. ErdH{o}s, A. R'enyi and V.T. S'os, Eds.), North-Holland, London, 1970, pp. 601-623. [14] S. Hedetniemi, Homomorphism of graphs and automata, Univ. Michigan Technical Report 03105-44-T, 1966. [15] W. Imrich, S. Klavv{z}ar, Product Graphs : Structure and Recognition, Wiley, New York, 2000. [16] S. Irani and V. Leung, Scheduling with conflicts and applications to traffic signal control, in: Proc. of Seventh Annu. ACM-SIAM Symp. on Discrete Algorithms, Atlanta, GA SIAM, Philadelphia, PA, 1996, pp. 85-94. [17] S. Janson and A. Ruci'nski, The infamous upper tail, Random Structures and Algorithms 20 (2002), No. 3, 317-342. [18] P. K. Jha, Hypercubes, median graphs and products of graphs : Some Algorithmic and Combinatorial Results, Ph.D. Thesis, Iowa State Univ., 1990. [19] H.A. Kierstead and A.V. Kostochka, A short proof of the Hajnal-Szemer'edi Theorem on equitable coloring, Combin. Probab. Comput. 17 (2008), No. 2, 265-270. [20] H.A. Kierstead and A.V. Kostochka, An Ore-type theorem on equitable coloring, J. Combin. Theory, Ser. B 98 (2008), 226-234. [21] F. Kitagawa and H. Ikeda, An existential problem of a weight-controlled subset and its application to schedule timetable construction, Discrete Math. 72 (1988), No. 1-3, 195-211. [22] S. Klavv{z}ar, Coloring graph products - A survey, Discrete Math. 155 (1996), No. 1-3, 135-145. [23] A.V. Kostochka, Equitable colorings of outerplanar graphs, Discrete Math. 258 (2002), No. 1-3, 373-377. [24] A.V. Kostochka and K. Nakprasit, Equitable coloring of $k$-degenerate graphs, Combin., Probab. Comput. 12 (2003), 53-60. [25] A.V. Kostochka and K. Nakprasit, On equitable $Delta$-coloring of graphs with low average degree, Theoret. Comput. Sci. 349 (2005), No. 1, 82-91. [26] A.V. Kostochka, K. Nakprasit and S.V. Pemmaraju, On equitable coloring of $d$-degenerate graphs, SIAM J. Discrete Math. 19 (2005), No. 1, 83-95. [27] A.V. Kostochka, M.J. Pelsmajer and D.B. West, A list analogue of equitable coloring, J. Graph Theory 44 (2003), No. 3, 166-177. [28] M. Kubale, Graph Colorings, American Mathematical Society, Providence, Rhode Island (2004). [29] P.C.B. Lam, W.C. Shiu, C.S. Tong, C.F. Zhang, On the equitable chromatic number of complete n-partite graphs, Discrete Appl. Math. 113 (2001), No. 2-3, 307-310. [30] K.-W. Lih, The equitable coloring of graphs, in: Handbook of Combinatorial Optimization (D.-Z. Du, P. Pardalos, Eds.), Vol. 3, Kluwer, Dordrecht, 1998, pp. 543-566. [31] K.-W. Lih, and P.-L. Wu, On equitable coloring of bipartite graphs, Discrete Math. 151 (1996), No. 1-3, 155-160. [32] W. Meyer, Equitable coloring, Amer. Math. Monthly 80 (1973), 920-022. [33] M. Mydlarz and E. Szemer'edi, Algorithmic Brooks' theorem, manuscript. [34] M.J. Pelsmajer, Equitable list-coloring for graphs of maximum degree 3, J. Graph Theory 47 (2004), No. 1, 1-8. [35] S.V. Pemmaraju, Equitable colorings extend Chernoff-Hoeffding bounds, in: Proc. Fifth Internat. Workshop on Randomization and Approximation Techniques in Computer Sciences, APPROX-RANDOM 2001, pp. 285-296. [36] G. Sabidussi, Graphs with given group and given graph-theoretical properties, Canad. J. Math. 9 (1957), 515-525. [37] B.F. Smith, P.E. Bjorstad and W.D. Gropp, Domain decomposition, Parallel Multilevel Methods for Elliptic Partial Differential Equations, Cambridge University Press, Cambridge, 1996, pp. 224. [38] S. Stahl, n-tuple colorings and associated graphs, J. Combin. Theory Ser. B 20 (1976), 185-203. [39] A. Tucker, Perfect graphs and an application to optimizing municipal services, SIAM Rev. 15 (1973), 585-590. [40] K. Vesztergombi, Some remarks on the chromatic number of the strong product of graphs, Colloq. Math. Soc. Janos Bolyai 25 (1997), 143-149. [41] V. G. Vizing, The Cartesian product of graphs, Vyv{c}isl. Sistemy 9 (1963), 30-43. [42] W.-FWang and K.-W. Lih, Equitable list coloring of graphs, Taiwanese J. Math. 8 (2004), No. 4, 747-759. [43] W.-F. Wang and K.-M. Zhang, Equitable colorings of line graphs and complete $r$-partite graphs, System Sci. Math. Sci. 13 (2000), No. 2, 190-194. [44] D. B. West, Introduction to Graph Theory, Prentice Hall, 2nd Ed., 2001. [45] H.-P. Yap and Y. Zhang, On equitable Colourings of graphs, manuscript 1996. [46] H.-P. Yap and Y. Zhang, The $Delta$-equitable colouring conjecture holds for outerplanar graphs, Bull. Inst. Math. Acad. Sinica 25 (1997) No. 2, 143-149. [47] H.-P. Yap and Y. Zhang, Equitable colourings of planar graphs, J. Combin. Math. Combin. Comput. 27 (1998), 97-105. [48] X. Zhu, A survey on Hedetniemi's conjecture, Taiwanese J. Math. 2 (1998), No. 1, 1-24. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/44992 | - |
| dc.description.abstract | 對正整數 $k$, 如果我們能將一個圖 $G$ 中所有的點著 $k$ 種顏色, 使得兩個相鄰的點所著的顏色相異, 而且任兩種顏色類在數量上差距最多一個, 則我們稱圖 $G$ 是均勻 $k$-可著的. 一個圖 $G$ 的均勻著色數, 記為 $chi_=(G)$, 是最小的 $k$ 使得 $G$ 是均勻 $k$-可著的. 一個圖 $G$ 的均勻著色臨界值, 記為 $chi_=^*(G)$, 是最小的 $t$ 使得對任何 $k$ 大於 $t$, $G$ 都是均勻 $k$-可著的.
乘積圖已在圖上的作用與結構的參數上有廣泛的研究, 包括圖著色. 而均勻著色是著色的變化型中在現實上有著較多應用之一 --- 所有顏色出現的頻率相互接近. 本文中我們研究 Cartesian 乘積圖, Kronecker 乘積圖, 與強乘積圖的均勻著色數與均勻著色臨界值. 特別地, 我們給出路徑, 圓圈, 完全圖, 與完全二部圖的這三類乘積圖均勻著色數與均勻著色臨界值的精確數值或上界. | zh_TW |
| dc.description.abstract | For a positive integer $k$, if we can color all vertices of $G$ in $k$ colors such that the colors of two adjacent vertices are different, and any two color classes are different in size at most one, then we call the graph $G$ equitably $k$-colorable. The equitable chromatic number of a graph $G$, denoted by $chi_=(G)$, is the minimum $k$ such that $G$ is equitably $k$-colorable. The equitable chromatic threshold of a graph $G$, denoted by $chi_=^*(G)$, is the minimum $t$ such that $G$ is equitably $k$-colorable for $k ge t$.
Graph products have been widely studied in many actions and parameters of the structure of graphs, including graph colorings. And the equitable coloring is one of the variations of colorings with more applications in real --- the frequency of the appearance of all colors are near to each other. In this thesis we study equitable chromatic numbers and equitable chromatic thresholds of Cartesian products, Kronecker products and strong products of graphs. In particular, we give exact values and upper bounds on equitable chromatic numbers and equitable chromatic thresholds of these three kinds of product of some classes of graphs such as paths, cycles, complete graphs and complete bipartite graphs. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-15T04:00:38Z (GMT). No. of bitstreams: 1 ntu-99-D92221001-1.pdf: 752596 bytes, checksum: 52bb4450735c281074b0c8dc86ca3dbe (MD5) Previous issue date: 2010 | en |
| dc.description.tableofcontents | Acknowledgements i
Abstract (in Chinese) ii Abstract (in English) iii Contents iv List of Figures vi 1 Introduction 1 1.1 Graph coloring 1 1.2 Equitable coloring 3 1.3 Graph product 6 1.4 Notation in graphs 8 1.5 A useful idea frequently used in the thesis 9 1.6 Summary 10 2 Cartesian Product of Graphs 11 2.1 Known results on Cartesian products 11 2.2 $C_{2ell+1}square G$ and $P_{2ell+1}square G$ for bipartite graph $G$ 13 2.3 $C_{2ell}square K_{m,n}$ and $P_{2ell}square K_{m,n}$ 14 2.4 Cartesian product of bipartite graphs 20 3 Kronecker Product of Graphs 28 3.1 Known results on Kronecker product of graphs 28 3.2 Kronecker product of graphs 30 3.3 Kronecker product of bipartite graphs 33 3.4 $C_n imes K_n$ and $P_m imes K_n$ 36 3.5 $P_2 imes K_n$, $P_3 imes K_n$, $C_3 imes K_n$, $C_4 imes K_n$, $K_{n,n,ldots,n}$ and $K_{n,2n}$ 43 3.6 Algorithms to compute $chi_=^*(K_{r(n)})$ and $chi_=^*(K_{n,2n})$ 50 4 Strong Product of Graphs 53 4.1 Known results on strong product of graphs 53 4.2 $C_moxtimes K_n$ and $P_moxtimes K_n$ 55 4.3 $C_moxtimes C_n$, $C_moxtimes P_n$ and $P_moxtimes P_n$ 58 5 Conclusion, Open Problems and Further Work 72 5.1 Conclusion 72 5.2 Open problems 74 5.3 Further work 76 Bibliography 77 | |
| dc.language.iso | en | |
| dc.subject | 強乘積圖 | zh_TW |
| dc.subject | Kronecker 乘積圖 | zh_TW |
| dc.subject | 均勻著色臨界值 | zh_TW |
| dc.subject | 均勻著色數 | zh_TW |
| dc.subject | 均勻著色 | zh_TW |
| dc.subject | Cartesian 乘積圖 | zh_TW |
| dc.subject | Kronecker product | en |
| dc.subject | equitable chromatic number | en |
| dc.subject | equitable coloring | en |
| dc.subject | equitable chromatic threshold | en |
| dc.subject | strong product | en |
| dc.subject | Cartesian product | en |
| dc.title | 乘積圖的均勻著色 | zh_TW |
| dc.title | Equitable colorings of graph products | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 98-2 | |
| dc.description.degree | 博士 | |
| dc.contributor.oralexamcommittee | 朱緒鼎,葉鴻國,傅恆霖,黃華民,顏經和,林強 | |
| dc.subject.keyword | Cartesian 乘積圖,Kronecker 乘積圖,強乘積圖,均勻著色,均勻著色數,均勻著色臨界值, | zh_TW |
| dc.subject.keyword | Cartesian product,Kronecker product,strong product,equitable coloring,equitable chromatic number,equitable chromatic threshold, | en |
| dc.relation.page | 81 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2010-02-24 | |
| dc.contributor.author-college | 理學院 | zh_TW |
| dc.contributor.author-dept | 數學研究所 | zh_TW |
| 顯示於系所單位： | 數學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-99-1.pdf 未授權公開取用 | 734.96 kB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。