Let Δ ≥ 4 be an integer. In this note, we prove that every planar graph with maximum degree Δ and girth at least 1 Δ+46 is strong (2Δ−1)-edgecolorable, that is best possible (in terms of number of colors) as soon as G contains two adjacent vertices of degree Δ. This improves [6] when Δ ≥ 6.
@article{bwmeta1.element.doi-10_7151_dmgt_1763,
author = {Gerard Jennhwa Chang and Mickael Montassier and Arnaud P\^eche and Andr\'e Raspaud},
title = {Strong Chromatic Index Of Planar Graphs With Large Girth},
journal = {Discussiones Mathematicae Graph Theory},
volume = {34},
year = {2014},
pages = {723-733},
zbl = {1303.05063},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1763}
}
Gerard Jennhwa Chang; Mickael Montassier; Arnaud Pêche; André Raspaud. Strong Chromatic Index Of Planar Graphs With Large Girth. Discussiones Mathematicae Graph Theory, Tome 34 (2014) pp. 723-733. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1763/
[1] L.D. Andersen, The strong chromatic index of a cubic graph is at most 10, Discrete Math. 108 (1992) 231-252. doi:10.1016/0012-365X(92)90678-9
[2] K. Appel and W. Haken, Every planar map is four colorable. Part I. Discharging, Illinois J. Math. 21 (1977) 429-490. | Zbl 0387.05009
[3] K. Appel and W. Haken, Every planar map is four colorable. Part II. Reducibility, Illinois J. Math. 21 (1977) 491-567. | Zbl 0387.05010
[4] C.L. Barrett, G. Istrate, V.S.A. Kumar, M.V. Marathe, S. Thite, and S. Thulasidasan, Strong edge coloring for channel assignment in wireless radio networks, in: Proc. of the 4th Annual IEEE International Conference on Pervasive Computing and Communications Workshops (2006) 106-110.
[5] N. Biggs, Some odd graph theory, Annals New York Academy of Sciences 319 (1979) 71-81. | Zbl 0479.05039
[6] 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 (2013) 759-770. doi:10.7151/dmgt.1708 | Zbl 1301.05118
[7] D.W. Cranston, Strong edge-coloring of graphs with maximum degree 4 using 22 colors, Discrete Math. 306 (2006) 2772-2778. doi:10.1016/j.disc.2006.03.053 | Zbl 1143.05025
[8] P. Erdős, Problems and results in combinatorial analysis and graph theory, Discrete Math. 72 (1988) 81-92. doi:10.1016/0012-365X(88)90196-3
[9] P. Erdős and J. Nešetřil, Problem, in: Irregularities of Partitions, G. Hal´asz and V.T. S´os (Eds.) (Springer, Berlin, 1989) 162-163.
[10] R.J. Faudree, A. Gyárfas, R.H. Schelp and Zs. Tuza, The strong chromatic index of graphs, Ars Combin. 29B (1990) 205-211. | Zbl 0721.05018
[11] J.L. Fouquet and J.L. Jolivet, Strong edge-coloring of graphs and applications to multi-k-gons, Ars Combin. 16 (1983) 141-150. | Zbl 0536.05027
[12] J.L. Fouquet and J.L. Jolivet, Strong edge-coloring of cubic planar graphs, Progress in Graph Theory (Waterloo 1982), (1984) 247-264.
[13] H. Grötzsch, Ein Dreifarbensatz für Dreikreisfreie Netze auf der Kugel , Math.-Nat. Reihe 8 (1959) 109-120.
[14] H. Hocquard, P. Ochem and P. Valicov, Strong edge coloring and induced matchings, LaBRI Research Report, 2011. http://hal.archives-ouvertes.fr/hal-00609454_v1/ | Zbl 1284.68281
[15] P. Horák, H. Qing, and W.T. Trotter, Induced matchings in cubic graphs, J. Graph Theory 17 (1993) 151-160. doi:10.1002/jgt.3190170204 | Zbl 0787.05038
[16] M. Mahdian, The strong chromatic index of graphs, Master Thesis (University of Toronto, Canada, 2000). | Zbl 0961.05022
[17] M. Molloy and B. Reed, A bound on the strong chromatic index of a graph, J. Combin. Theory (B) 69 (1997) 103-109. doi:10.1006/jctb.1997.1724
[18] T. Nandagopal, T. Kim, X. Gao and V. Bharghavan, Achieving MAC layer fairness in wireless packet networks, in: Proc. 6th ACM Conf. on Mobile Computing and Networking (2000) 87-98.
[19] J. Nešetřil, A. Raspaud and A. Sopena, Colorings and girth of oriented planar graphs, Discrete Math. 165-166 (1997) 519-530. doi:10.1016/S0012-365X(96)00198-7 | Zbl 0873.05042
[20] S. Ramanathan, A unified framework and algorithm for (T/F/C) DMA channel assignment in wireless networks, in: Proc. IEEE INFOCOM’97 (1997) 900-907. doi:10.1109/INFCOM.1997.644573
[21] S. Ramanathan and E.L. Lloyd, Scheduling algorithms for multi-hop radio networks, in: IEEE/ACM Trans. Networking 2 (1993) 166-177. doi:10.1109/90.222924
[22] D.P. Sanders and Y. Zhao, Planar graphs of maximum degree seven are Class 1, J. Combin. Theory (B) 83 (2001) 201-212. doi:1006/jctb.2001.2047 | Zbl 1024.05031
[23] V.G. Vizing, On an estimate of the chromatic class of a p-graph, Diskret. Analiz. 3 (1964) 25-30.