臺灣博碩士論文加值系統

(44.210.99.209) 您好！臺灣時間：2024/04/15 16:24

:::

詳目顯示

:

• 被引用: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.
 摘要 iAbstract iiContents iiiList of Figures ivList of Tables v1 Introduction 12 The proof of the main theorem 53 The key lemma: caterpillar with edge pre-coloring 84 Refinement of the key lemma and its consequences 145 Consequences concerning the maximum average degree 18Bibliography 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.
 國圖紙本論文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 無相關論文

 無相關期刊

 1 圖的覆蓋問題之研究 2 蜘蛛圖的反魔方標號 3 以複合式模型學習法探究多社群網路媒體之使用者資訊 4 研發根管治療用生醫活性材料:結晶機制與封閉側根管及分支 5 Neutrophil gelatinase-associated lipocalin作為貓隻腎臟疾病的生物標記 6 脂膜筏及Caveolin藉由Src引導纖維母細胞於電場中之方向性移動 7 人體組織生物列印之三維電腦輔助設計模型建構 8 農民使用電子商務銷售農產品之影響因素分析 9 文本標記格式的轉換與應用 10 紐幣匯率變動因素之實證研究 11 房地合一課稅對營建業股價影響之事件研究 12 二維拓樸絕緣體的電子自旋操控 13 溫度效應對二元鈦-矽氧化物薄膜電子特性的影響 14 第三方支付法：網路金融之監理與自律 15 多孔球粒子之振盪電泳行為與介電泳現象

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室