Geodesic
Precise Upper Bound for the Strong Edge Chromatic Number of Sparse Planar Graphs
Discussiones Mathematicae. Graph Theory, Tome 33 (2013) no. 4, pp. 759-770.

Voir la notice de l'article provenant de la source Library of Science

We prove that every planar graph with maximum degree Δ is strong edge (2 Δ − 1)-colorable if its girth is at least 40 [ Δ/2 ] +1. The bound 2 Δ −1 is reached at any graph that has two adjacent vertices of degree Δ .
Keywords: planar graph, edge coloring, 2-distance coloring, strong edgecoloring 
@article{DMGT_2013_33_4_a10,
     author = {Borodin, Oleg V. and Ivanova, Anna O.},
     title = {Precise {Upper} {Bound} for the {Strong} {Edge} {Chromatic} {Number} of {Sparse} {Planar} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {759--770},
     publisher = {mathdoc},
     volume = {33},
     number = {4},
     year = {2013},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2013_33_4_a10/}
}
TY  - JOUR
AU  - Borodin, Oleg V.
AU  - Ivanova, Anna O.
TI  - Precise Upper Bound for the Strong Edge Chromatic Number of Sparse Planar Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2013
SP  - 759
EP  - 770
VL  - 33
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2013_33_4_a10/
LA  - en
ID  - DMGT_2013_33_4_a10
ER  - 
%0 Journal Article
%A Borodin, Oleg V.
%A Ivanova, Anna O.
%T Precise Upper Bound for the Strong Edge Chromatic Number of Sparse Planar Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2013
%P 759-770
%V 33
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2013_33_4_a10/
%G en
%F DMGT_2013_33_4_a10
Borodin, Oleg V.; Ivanova, Anna O. Precise Upper Bound for the Strong Edge Chromatic Number of Sparse Planar Graphs. Discussiones Mathematicae. Graph Theory, Tome 33 (2013) no. 4, pp. 759-770. http://geodesic.mathdoc.fr/item/DMGT_2013_33_4_a10/

[1] G. Agnarsson and M.M. Halldorsson, Coloring powers of planar graphs, SIAM J. Discrete Math. 16 (2003) 651-662. doi:10.1137/S0895480100367950

[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

[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).

[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).

[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

[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

[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

[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

[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).

[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).

[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).

[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

[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

[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

[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

[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

[18] F. Havet, Choosability of the square of planar subcubic graphs with large girth, Discrete Math. 309 (2009) 3353-3563.

[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

[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.

[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).

[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).

[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

[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

[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

[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:1(67::AID-JGT6)3.0.CO;2-C

[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