請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/4051
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 張鎮華(Gerard Jennhwa Chang) | |
dc.contributor.author | Guan-Huei Duh | en |
dc.contributor.author | 杜冠慧 | zh_TW |
dc.date.accessioned | 2021-05-13T08:41:15Z | - |
dc.date.available | 2017-08-31 | |
dc.date.available | 2021-05-13T08:41:15Z | - |
dc.date.copyright | 2016-08-31 | |
dc.date.issued | 2016 | |
dc.date.submitted | 2016-08-29 | |
dc.identifier.citation | [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. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/4051 | - |
dc.description.abstract | 一個圖 $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)$ 就會恰好是此圖的強邊著色數。本結果反映出大腰圍的平面圖局部上有看似樹的結構。 | zh_TW |
dc.description.abstract | 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. | en |
dc.description.provenance | Made available in DSpace on 2021-05-13T08:41:15Z (GMT). No. of bitstreams: 1 ntu-105-R03221028-1.pdf: 421325 bytes, checksum: 11452bcc5d2d69c104c51bf45a3b56db (MD5) Previous issue date: 2016 | en |
dc.description.tableofcontents | 摘要 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 | |
dc.language.iso | en | |
dc.title | 大腰圍平面圖的強邊著色數之精確值 | zh_TW |
dc.title | On the precise value of the strong chromatic-index of a planar graph with a large girth | en |
dc.type | Thesis | |
dc.date.schoolyear | 104-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 顏經和,郭大衛 | |
dc.subject.keyword | 強邊著色數,平面圖,腰圍, | zh_TW |
dc.subject.keyword | Strong chromatic index,planar graph,girth, | en |
dc.relation.page | 23 | |
dc.identifier.doi | 10.6342/NTU201603561 | |
dc.rights.note | 同意授權(全球公開) | |
dc.date.accepted | 2016-08-29 | |
dc.contributor.author-college | 理學院 | zh_TW |
dc.contributor.author-dept | 數學研究所 | zh_TW |
顯示於系所單位: | 數學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-105-1.pdf | 411.45 kB | Adobe PDF | 檢視/開啟 |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。