We prove that every planar graph with maximum degree ∆ is strong edge (2∆−1)-colorable if its girth is at least 40 [...] +1. The bound 2∆−1 is reached at any graph that has two adjacent vertices of degree ∆.
@article{bwmeta1.element.doi-10_7151_dmgt_1708,
author = {Oleg V. Borodin and Anna O. Ivanova},
title = {Precise Upper Bound for the Strong Edge Chromatic Number of Sparse Planar Graphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {33},
year = {2013},
pages = {759-770},
zbl = {1301.05118},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1708}
}
Oleg V. Borodin; Anna O. Ivanova. Precise Upper Bound for the Strong Edge Chromatic Number of Sparse Planar Graphs. Discussiones Mathematicae Graph Theory, Tome 33 (2013) pp. 759-770. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1708/
[1] G. Agnarsson and M.M. Halldorsson, Coloring powers of planar graphs, SIAM J. Discrete Math. 16 (2003) 651-662. doi:10.1137/S0895480100367950[Crossref] | Zbl 1029.05047
[2] 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[Crossref]
[3] O.V. Borodin, H.J. Broersma, A.N. Glebov and J. van den Heuvel, The minimum degree and chromatic number of the square of a planar graph, Diskretn. Anal. Issled. Oper. 8 (2001) 9-33 (in Russian). | Zbl 1012.05074
[4] O.V. Borodin, H.J. Broersma, A.N. Glebov and J. van den Heuvel The structure of plane triangulations in terms of stars and bunches, Diskretn. Anal. Issled. Oper. 8 (2001) 15-39 (in Russian).
[5] O.V. Borodin, A.N. Glebov, A.O. Ivanova, T.K. Neustroeva and V.A. Tashkinov, Sufficient conditions for the 2-distance (_ + 1)-colorability of plane graphs, Sib. Elektron. Mat. Izv. 1 (2004) 129-141 (in Russian). | Zbl 1076.05032
[6] O.V. Borodin and A.O. Ivanova, 2-distance (_ + 2)-coloring of planar graphs with girth six and _ ≥ 18, Discrete Math. 309 (2009) 6496-6502. doi:10.1016/j.disc.2009.06.029[Crossref] | Zbl 1184.05040
[7] O.V. Borodin and A.O. Ivanova, List 2-distance (_ + 2)-coloring of planar graphs with girth six , European J. Combin. 30 (2009) 1257-1262. doi:10.1016/j.ejc.2008.12.019[Crossref][WoS] | Zbl 1190.05055
[8] O.V. Borodin and A.O. Ivanova, 2-distance 4-colorability of planar subcubic graphs with girth at least 22, Discuss. Math. Graph Theory 32 (2012) 141-151. doi:10.7151/dmgt.1592[Crossref] | Zbl 1255.05075
[9] O.V. Borodin and A.O. Ivanova, List 2-facial 5-colorability of plane graphs with girth at least 12, Discrete Math. 312 (2012) 306-314. doi:10.1016/j.disc.2011.09.018[WoS][Crossref] | Zbl 1233.05098
[10] O.V. Borodin, A.O. Ivanova, and T.K. Neustroeva, 2-distance coloring of sparse plane graphs, Sib. Elektron. Mat. Izv. 1 (2004) 76-90 (in Russian). | Zbl 1077.05040
[11] O.V. Borodin, A.O. Ivanova and T.K. Neustroeva, Sufficient conditions for 2- distance (_ + 1)-colorability of planar graphs of girth 6 , Diskretn. Anal. Issled. Oper. 12(3) (2005) 32-47 (in Russian). | Zbl 1249.05113
[12] O.V. Borodin, A.O. Ivanova and T.K. Neustroeva, Sufficient conditions for the minimum 2-distance colorability of planar graphs with girth 6, Sib. Elektron. Mat. Izv. 3 (2006) 441-450 (in Russian). | Zbl 1119.05039
[13] 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[Crossref] | Zbl 1143.05025
[14] D.W. Cranston and S.-J. Kim, List-coloring the square of a subcubic graph, J. Graph Theory 57 (2008) 65-87. doi:10.1002/jgt.20273[Crossref] | Zbl 1172.05023
[15] Z. Dvořák, D. Kràl, P. Nejedlý and R. Škrekovski, Coloring squares of planar graphs with girth six , European J. Combin. 29 (2008) 838-849. doi:10.1016/j.ejc.2007.11.005[WoS][Crossref] | Zbl 1143.05027
[16] Z. Dvořák, R. Škrekovski and M. Tancer, List-coloring squares of sparse subcubic graphs, SIAM J. Discrete Math. 22 (2008) 139-159. doi:10.1137/050634049[Crossref][WoS] | Zbl 1159.05018
[17] R.J. Faudree, A. Gyárfás, R.H. Schelp and Zs. Tuza, The strong chromatic index of graphs, Ars Combin. 29B (1990) 205-211. doi:10.1016/j.disc.2007.12.100[Crossref] | Zbl 0721.05018
[18] F. Havet, Choosability of the square of planar subcubic graphs with large girth, Discrete Math. 309 (2009) 3353-3563.[WoS] | Zbl 1213.05084
[19] F. Havet, J. van den Heuvel, C. McDiarmid and B. Reed, List colouring squares of planar graphs, European Conference on Combinatorics, Graph Theory and Applications, Eurocomb 2007 ( Sevilla, Spain, September, 2007) www-sop.inria.fr/members/Frederic.Havet/habilitation/ext-abstr.pdf | Zbl 05284956
[20] F. Havet, J. van den Heuvel, C. McDiarmid and B. Reed, List colouring squares of planar graphs, INRIA Research Report no. RR-6586 (2008).
[21] P. Horák, The strong chromatic index of graphs with maximum degree four , Contemp. Methods in Graph Theory (1990) 399-403. | Zbl 0715.05023
[22] A.O. Ivanova, List 2-distance (_ + 1)-coloring of planar graphs with girth at least 7, Diskretn. Anal. Issled. Oper. 17(5) (2010) 22-36 (in Russian). | Zbl 1249.05118
[23] A.O. Ivanova and A.S. Solovéva, 2-Distance (_+2)-coloring of sparse planar graphs with _ = 3 , Mathematical Notes of Yakutsk University 16(2) (2009) 32-41(in Russian). | Zbl 1274.05165
[24] T. Jensen and B. Toft, Graph Coloring Problems (New York: John Willey & Sons, 1995).
[25] M. Molloy and M.R. Salavatipour, Frequency channel assignment on planar networks, in: LNCS, vol. 2461, R.H. Mohring and R. Raman (Eds.)(Springer 2002) 736-747. doi:10.1007/3-540-45749-6 64[Crossref] | Zbl 1040.90034
[26] M. Molloy and M.R. Salavatipour, A bound on the chromatic number of the square of a planar graph, J. Combin. Theory (B) 94 (2005) 189-213. doi:10.1016/j.jctb.2004.12.005[Crossref]
[27] M. Montassier and A. Raspaud, A note on 2-facial coloring of plane graphs, Inform.Process. Lett. 98 (2006) 235-241. doi:10.1016/j.ipl.2006.02.013[Crossref] | Zbl 1178.05042
[28] D.P. Sanders and Y. Zhao, On total 9-colouring planar graphs of maximum degree seven, J. Graph Theory 31 (1999) 67-73. doi:10.1002/(SICI)1097-0118(199905)31:1h67::AID-JGT6i3.0.CO;2-C[Crossref]
[29] V.G. Vizing, On an estimate of the chromatic index of a p-graph, Diskret. Analiz 3 (1964) 25-30 (in Russian).
[30] V.G. Vizing, Critical graphs with given chromatic index, Metody Diskret. Analiz 5 (1965) 9-17 (in Russian).
[31] G. Wegner, Graphs with given diameter and a coloring problem, Technical Report (University of Dortmund, Germany, 1977).
[32] D.B. West, Strong edge-coloring (Open Problems-Graph Theory and Combinatorics, http://www.math.uiuc.edu/west/openp/strongedge.html, 2003).
[33] L. Zhang, Every planar graph with maximum degree 7 is of class 1, Graphs Combin. 16 (2000) 467-495. doi:10.1007/s003730070009 [Crossref] | Zbl 0988.05042