跳到主要內容

臺灣博碩士論文加值系統

(44.210.99.209) 您好!臺灣時間:2024/04/15 16:24
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:杜冠慧
研究生(外文):Guan-Huei Duh
論文名稱:大腰圍平面圖的強邊著色數之精確值
論文名稱(外文):On the precise value of the strong chromatic-index of a planar graph with a large girth
指導教授:張鎮華張鎮華引用關係
指導教授(外文):Gerard Jennhwa Chang
口試委員:顏經和郭大衛
口試日期:2016-07-01
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:數學研究所
學門:數學及統計學門
學類:數學學類
論文種類:學術論文
論文出版年:2016
畢業學年度:104
語文別:英文
論文頁數:23
中文關鍵詞:強邊著色數平面圖腰圍
外文關鍵詞:Strong chromatic indexplanar graphgirth
相關次數:
  • 被引用被引用:0
  • 點閱點閱:219
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
一個圖 $G$ 的 $k$-強邊著色指的是使得距離為二以內的邊都塗不同顏色的 $k$-邊著色;強邊著色數 $chi''_s(G)$ 則標明參數 $k$ 的最小可能。此概念最初是為了解決平地上設置廣播網路的問題,由 Fouquet 與 Jolivet 提出。對於任意圖 $G$,參數 $sigma(G)=max_{xyin E(G)}{deg(x)+deg(y)-1}$是強邊著色數的一個下界;且若 $G$ 是樹,則強邊著色數會到達此下界。另一方面,對於最大度數為 $Delta$ 的平面圖$G$,經由四色定理可以證得 $chi''_s(G)leq 4Delta+4$。更進一步,在各種腰圍與最大度數的條件下,平面圖的強邊著色數之上界分別有$4Delta$, $3Delta+5$, $3Delta+1$, $3Delta$ 和 $2Delta-1$ 等等優化。本篇論文說明當平面圖 $G$ 的腰圍夠大,且$sigma(G)geqDelta(G)+2$ 時,參數 $sigma(G)$ 就會恰好是此圖的強邊著色數。本結果反映出大腰圍的平面圖局部上有看似樹的結構。

A {em strong $k$-edge-coloring} of a graph $G$ is a mapping from the edge set $E(G)$ to ${1,2,ldots,k}$ such that every pair of distinct edges at distance at most two receive different colors. The {it strong chromatic index} $chi''_s(G)$ of a graph $G$ is the minimum $k$ for which $G$ has a strong $k$-edge-coloring. The concept of strong edge-coloring was introduced by Fouquet and Jolivet to model the channel assignment in some radio networks. Denote the parameter $sigma(G)=max_{xyin E(G)}{deg(x)+deg(y)-1}$. It is easy to see that $sigma(G) le chi''_s(G)$ for any graph $G$, and the equality holds when $G$ is a tree. For a planar graph $G$ of maximum degree $Delta$, it was proved that $chi''_s(G) le 4 Delta +4$ by using the Four Color Theorem. The upper bound was then reduced to $4Delta$, $3Delta+5$, $3Delta+1$, $3Delta$, $2Delta-1$ under different conditions for $Delta$ and the girth. In this paper, we prove that if the girth of a planar graph $G$ is large enough and $sigma(G)geq Delta(G)+2$, then the strong chromatic index of $G$ is precisely $sigma(G)$. This result reflects the intuition that a planar graph with a large girth locally looks like a tree.

摘要 i
Abstract ii
Contents iii
List of Figures iv
List of Tables v
1 Introduction 1
2 The proof of the main theorem 5
3 The key lemma: caterpillar with edge pre-coloring 8
4 Refinement of the key lemma and its consequences 14
5 Consequences concerning the maximum average degree 18
Bibliography 20


[1] L. D. Andersen, The strong chromatic index of a cubic graph is at most 10, Discrete Math., 108(1-3):231–252, 1992.
[2] K. Appel and W. Haken, Every planar map is four colorable. Part I: Discharging, Illinois J. of Math., 21(3):429–490, 1977.
[3] K. Appel, W. Haken, and J. Koch, Every planar map is four colorable. Part II: Reducibility, Illinois J. of Math., 21(3):491–567, 1977.
[4] C. Barrett, G. Istrate, A. V. S. Kumar, M. Marathe, S. Thite, and S. Thulasidasan, Strong edge coloring for channel assignment in wireless radio networks, in PERCOMW’06: Proceedings of the 4th Annual IEEE International Conference on Pervasive Computing and Communications Workshops, pp. 106–110, IEEE Computer Society, Washington, DC, 2006.
[5] M. Basavaraju and M. C. Francis, Strong chromatic index of chordless graphs, J. Graph Theory, 80(1):58–68, 2015.
[6] J. Bensmail, A. Harutyunyan, H. Hocquard, and P. Valicov, Strong edge-colouring of sparse planar graphs, Discrete Appl. Math., 179:229–234, 2014.
[7] O. V. Borodin and A. O. Ivanova, Precise upper bound for the strong edge chromatic number of sparse planar graphs, Discuss. Math. Graph Theory, 33(4):759–770, 2013.
[8] H. Bruhn and F. Joos, A stronger bound for the strong chromatic index, preprint at arXiv: 1504.02583v1, 22 pages, 2015.
[9] G. J. Chang, S.-H. Chen, C.-Y. Hsu, C.-M. Hung, and H.-L. Lai, Strong edgecoloring for jellyfish graphs, Discrete Math., 338(12):2348–2355, 2015.
[10] G. J. Chang and D. D.-F. Liu, Strong edge-coloring for cubic Halin graphs, Discrete Math., 312(8):1468–1475, 2012.
[11] G. J. Chang, M. Montassier, A. Pêcher, and A. Raspaud, Strong chromatic index of planar graphs with large girth, Discuss. Math. Graph Theory, 34(4):723–733, 2014.
[12] G. J. Chang and N. Narayanan, Strong chromatic index of 2-degenerate graphs, J. Graph Theory, 73(2):119–126, 2013.
[13] D. W. Cranston, Strong edge-coloring of graphs with maximum degree 4 using 22 colors, Discrete Math., 306(21):2772–2778, 2006.
[14] D. W. Cranston, D. B. West, A guide to the discharging method, preprint at arXiv: 1306.4434v1, 77 pages, 2013.
[15] M. Dębski, J. Grytczuk, and M. Śleszyńska Nowak, The strong chromatic index of sparse graphs, Inform. Process. Lett., 115(2):326–330, 2015.
[16] P. Erdős, Problems and results in combinatorial analysis and graph theory, Discrete Math., 72(1-3):81–92, 1988.
[17] P. Erdős and J. Nešetřil. Problems, in Irregularities of Partitions, pp. 162–163, Springer, Berlin, 1989.
[18] R. J. Faudree, A. Gyárfás, R. H. Schelp, and Z. Tuza, The strong chromatic index of graphs, Ars Combin., 29B:205–211, 1990.
[19] J. L. Fouquet and J. L. Jolivet, Strong edge-colorings of graphs and applications to multi-k-gons, Ars Combin., 16:141–150, 1983.
[20] J. L. Fouquet and J. L. Jolivet, Strong edge-coloring of cubic planar graphs, in Progress in graph theory, pp. 247–264, Academic Press, Toronto, 1984.
[21] H. Grötzsch, Ein dreifarbensatz fur dreikreisfreie netze auf der kugel, Math.-Natur. Reihe, 8:109–120, 1959.
[22] P. Horák, H. Qing, and W. T. Trotter, Induced matchings in cubic graphs, J. Graph Theory, 17(2):151–160, 1993.
[23] D. Hudák, B. Luzar, R. Soták, and R. Skrekovski, Strong edge-coloring of planar graphs, Discrete Math., 324:41–49, 2014.
[24] J. Janssen and L. Narayanan, Approximation algorithms for channel assignment with constraints, Theoret. Comput. Sci., 262(1–2):649–667, 2001.
[25] H.-H. Lai, K.-W. Lih, and P.-Y. Tsai, The strong chromatic index of Halin graphs, Discrete Math., 312(9):1536–1541, 2012.
[26] K.-W. Lih and D. D.-F. Liu, On the strong chromatic index of cubic Halin graphs, Appl. Math. Lett., 25(5):898–901, 2012.
[27] M. Mahdian, The strong chromatic index of C_4-free graphs, Random Structures Algorithms, 17(3-4):357–375, 2000.
[28] M. Molloy and B. Reed, A bound on the strong chromatic index of a graph, J. Combin. Theory Ser. B, 69(2):103–109, 1997.
[29] T. Nandagopal, T.-E. Kim, X. Gao, and V. Bharghavan, Achieving MAC layer fairness in wireless packet networks, in MobiCom ’00: Proceedings of the 6th Annual International Conference on Mobile Computing and Networking, pp. 87–98, ACM, New York, 2000.
[30] J. Nešetřil, A. Raspaud, and E. Sopena, Colorings and girth of oriented planar graphs, Discrete Math., 165/166:519–530, 1997.
[31] S. Ramanathan, A unified framework and algorithm for channel assignment in wireless networks, Wireless Networks, 5(2):81–94, 1999.
[32] S. Ramanathan and E. L. Lloyd, Scheduling algorithms for multihop radio networks, IEEE/ACM Transactions on Networking, 1(2):166–177, 1993.
[33] D. P. Sanders and Y. Zhao, Planar graphs of maximum degree seven are class I, J. Combin. Theory Ser. B, 83(2):201–212, 2001.
[34] W. C. Shiu, P. C. B. Lam, and W. K. Tam, On strong chromatic index of Halin graphs, J. Combin. Math. Combin. Comput., 57:211–222, 2006.
[35] W. C. Shiu and W. K. Tam, The strong chromatic index of complete cubic Halin graphs, Appl. Math. Lett., 22(5):754–758, 2009.
[36] H. Tamura, K. Watanabe, M. Sengoku, and S. Shinoda, A channel assignment problem in multihop wireless networks and graph theory, J. Circuits Systems Comput., 13(02):375–385, 2004.
[37] O. Togni, Strong chromatic index of products of graphs, Discrete Math. Theor. Comput. Sci., 9(1):47–56, 2007.
[38] V. G. Vizing, Critical graphs with given chromatic class, Diskret. Analiz, 5:9–17, 1965.
[39] T. Wang, Strong chromatic index of k-degenerate graphs, Discrete Math., 330:17–19, 2014.
[40] T. Wang and X. Zhao, Odd graph and its application on the strong edge coloring, preprint at arXiv: 1412.8358v3, 7 pages, 2015.
[41] G. Yu, Strong edge-colorings for k-degenerate graphs, Graphs Combin., 31(5):1815–1818, 2015.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top