DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2023): 0.5

5-year Journal Impact Factor (2023): 0.6

CiteScore (2023): 2.2

SNIP (2023): 0.681

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 33(4) (2013) 759-770
DOI: https://doi.org/10.7151/dmgt.1708

Precise upper bound for the strong edge chromatic number of sparse planar graphs

Oleg V. Borodin

Institute of Mathematics
Siberian Branch of the Russian Academy of Sciences
and
Novosibirsk State University, Novosibirsk, 630090, Russia

Anna O. Ivanova

Institute of Mathematics of
Ammosov North-Eastern Federal University
Yakutsk, 677891, Russia

Abstract

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 edge-coloring

2010 Mathematics Subject Classification: 05C15.

References

[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).
http://hal.inria.fr/inria-00303303/.
[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'eva, 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.

Received 4 November 2011
Revised 20 September 2012
Accepted 20 September 2012

Close