臺灣博碩士論文加值系統

在圖G = (V(G), E(G))上關聯被表示為(v,e)，v ∈ V(G)、e ∈ E(G)且v為e連接的一個點，兩個關聯處(v,e)和(w,f)的相鄰規則如下：(a) v = w、(b) e = f或(c) vw = e or vw = f，符合其中一個規則就為相鄰。令I(G)為一個全部關聯處所組成的集合。在圖G上適當的關聯著色是由I(G)映射到一個顏色集合，且相鄰的關聯處分配到不同的顏色。若用最少的顏色數來完成圖G的適當關聯著色，則稱為關聯著色數，表示為χi(G)。
在本篇論文中，我們研究廣義彼得森圖GP(n, k)與弦環圖CR(N, d)的關聯著色，首先在GP(n, k)上，我們確定4 ≤ χi(GP(n, k)) ≤ 5，此外我們提出如下結果：(i)若n為奇數時，則χi(GP(n,k)) = 5、(ii)χi(GP(n,2)) = 5以及(iii)若n ≡ 0 (mod 4)且k是奇數，則χi(GP(n,k)) = 4。
接著在CR(N, d)上，提出如下結果：(i)若N ≡ 0 (mod 5)且d = 2或3，則χi(CR(N, d)) = 5、(ii) 若N mod 5 ∈ {1,2,3,4}，則χi(CR(N, 2)) = 6以及(iii) 若N ≡ 2 (mod 5)，則χi(CR(N, 3)) = 6。

An incidence of G is a pair (v, e) where v ∈ V(G) is a vertex and e ∈ E(G) is an edge incident with v. Two incidences (v, e) and (w, f) are adjacent if one of the following holds: (a) v = w, (b) e = f or (c) vw = e or vw = f. Let I(G) be the set consisting of all incidences of a graph G. A proper incidence coloring of G is a mapping from I(G) to a set of colors such that adjacent incidences are assigned distinct colors. The smallest number of colors required for such a coloring is called the incidence coloring number of G, and is denoted by χi(G).
In this paper, we study the incidence coloring on generalized Petersen graphs GP(n, k) and Chordal Rings CR(N, d). We first assure that 4 ≤ χi(GP(n, k)) ≤ 5. Furthermore, we provide the following results: (i) χi(GP(n, k)) = 5 if n is odd, (ii) χi(GP(n, 2)) = 5, and (iii) χi(GP(n, k)) = 4 if n ≡ 0 (mod 4) and k is odd.
Then, we have the following results on χi(CR(N, d)): (i) χi(CR(N, d)) = 5, if N ≡ 0 (mod 5) and d = 2 or 3, (ii) χi(CR(N, 2)) = 6, if N mod 5 ≠ 0, and (iii) χi(CR(N, 3)) = 6, if N ≡ 2 (mod 5).

明志科技大學碩士學位論文 指導教授推薦書 i
明志科技大學碩士學位論文 口試委員會審定書 ii
誌謝 iii
中文摘要 iv
Abstract v
目錄 vi
表目錄 viii
圖目錄 ix
第一章 緒論 1
1.1 研究背景 1
1.2 研究動機與目的 1
1.3 圖形符號 2
1.4 點著色問題 2
1.5 邊著色問題 3
1.6 關聯著色問題 4
1.7 廣義彼得森圖 5
1.8 弦環圖 6
第二章 文獻探討 7
2.1 在完全圖求解關聯著色問題 7
2.2 在樹上求解關聯著色問題 8
2.3 在完全二分圖中求解關聯著色問題 9
2.4 在網格圖中求解關聯著色問題 11
第三章 在廣義彼得森圖中求解關聯著色問題 17
3.1 廣義彼得森圖GP(n, k)之漢彌爾頓路徑 17
3.2 廣義彼得森圖GP(n, k)之關聯著色問題 18
3.3 廣義彼得森圖GP(n, 2)之關聯著色數 21
3.4 廣義彼得森圖GP(n, k)之4-關聯著色 22
3.5 廣義彼得森圖GP(n, k)的關聯著色之整理 24
第四章 在弦環圖中求解關聯著色問題 25
4.1 弦環圖CR(N, d)之關聯著色數下界值 25
4.2 弦環圖CR(N, 2)之關聯著色數 25
4.3 弦環圖CR(N, 3)之關聯著色數 31
4.4 弦環圖CR(N, d)的關聯著色數之整理 33
第五章 結論 35
參考文獻 36

Alspach, B. (1983). The classification of hamiltonian generalized Petersen graphs. Journal of Combinatorial Theory, Series B, 34(3), 293-312.
Arden, B. W., & Lee, H. (1981). Analysis of chordal ring network. Computers, IEEE Transactions on, 100(4), 291-295.
Bermond, J. C., Comellas, F., & Hsu, D. F. (1995). Distributed loop computer-networks: a survey. Journal of Parallel and Distributed Computing, 24(1), 2-10.
Brualdi, R. A., & Massey, J. J. Q. (1993). Incidence and strong edge colorings of graphs. Discrete Mathematics, 122(1), 51-58.
Ding K.F., Pai K.J., Chang J.M., and Tsaur R.H. (2015). Some Results of Incidence Coloring on Generalized Petersen Graphs, International Computer Symposium (ICS) Held at Taichung, December 12–14, 2014(274), 83-89.
Dolama, M. H., & Sopena, E. (2005). On the maximum average degree and the incidence chromatic number of a graph. Discrete Mathematics & Theoretical Computer Science, 7(1), 203-216.
Dolama M.H., Sopena É., and Zhu X. (2004). Incidence coloring of k-degenerated graphs,Discrete Math. 283, 121-128.
Guiduli, B. (1997). On incidence coloring and star arboricity of graphs. Discrete Mathematics, 163(1), 275-278.
Huang, C. I., Wang, Y. L., & Chung, S. S. (2004). The incidence coloring numbers of meshes. Computers & Mathematics with Applications, 48(10), 1643-1649.
Li, D., & Liu, M. (2008). Incidence coloring of the squares of some graphs.Discrete Mathematics, 308(24), 6569-6574.
Li, X., & Tu, J. (2008). NP-completeness of 4-incidence colorability of semi-cubic graphs. Discrete Mathematics, 308(7), 1334-1340.
Mans, B. (1999). On the interval routing of chordal rings. In Parallel Architectures, Algorithms, and Networks, 1999.(I-SPAN'99) Proceedings. Fourth InternationalSymposium on (pp. 16-21).
Maydanskiy, M. (2005). The incidence coloring conjecture for graphs of maximum degree 3. Discrete mathematics, 292(1), 131-141.
Meng, X., Guo, J., & Su, B. (2012). Incidence coloring of pseudo-Halin graphs.Discrete Mathematics, 312(22), 3276-3282.
Nakprasit, K., & Nakprasit, K. (2012). Incidence colorings of the powers of cycles. International Journal of Pure and Applied Mathematics, 76, 143-148.
Pai, K. J., Chang, J. M., Yang, J. S., & Wu, R. Y. (2014a). Incidence coloring on hypercubes. Theoretical Computer Science, 557, 59-65.
Pai, K. J., Chang, J. M., Yang, J. S., & Wu, R. Y. (2014b). On the incidence coloring number of folded hypercubes. In Computer Science and Engineering Conference (ICSEC), 2014 International (pp. 7-11).
Sun, P. K. (2012). Incidence coloring of regular graphs and complement graphs. Taiwanese Journal of Mathematics, 16(6), 2289-2295.
Shiu, W. C., Lam, P. C. B., & Chen, D. L. (2002). On incidence coloring for some cubic graphs. Discrete mathematics, 252(1), 259-266.
Sopena, É., & Wu, J. (2013). The incidence chromatic number of toroidal grids.Discussiones Mathematicae Graph Theory, 33(2), 315-327.
Watkins, M. E. (1969). A theorem on Tait colorings with an application to the generalized Petersen graphs. Journal of Combinatorial Theory, 6(2), 152-164.
Wu, J. (2009). Some results on the incidence coloring number of a graph.Discrete Mathematics, 309(12), 3866-3870.
Wang, S. D., Chen, D. L., & Pang, S. C. (2002). The incidence coloring number of Halin graphs and outerplanar graphs. Discrete mathematics, 256(1), 397-405.