Precise Upper Bound for the Strong Edge Chromatic Number of Sparse Planar Graphs

Oleg V. Borodin; Anna O. Ivanova

Discussiones Mathematicae Graph Theory (2013)

  • Volume: 33, Issue: 4, page 759-770
  • ISSN: 2083-5892

Abstract

top
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 ∆.

How to cite

top

Oleg V. Borodin, and Anna O. Ivanova. "Precise Upper Bound for the Strong Edge Chromatic Number of Sparse Planar Graphs." Discussiones Mathematicae Graph Theory 33.4 (2013): 759-770. <http://eudml.org/doc/267877>.

@article{OlegV2013,
abstract = {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 ∆.},
author = {Oleg V. Borodin, Anna O. Ivanova},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {planar graph; edge coloring; 2-distance coloring; strong edgecoloring; strong edge coloring},
language = {eng},
number = {4},
pages = {759-770},
title = {Precise Upper Bound for the Strong Edge Chromatic Number of Sparse Planar Graphs},
url = {http://eudml.org/doc/267877},
volume = {33},
year = {2013},
}

TY - JOUR
AU - Oleg V. Borodin
AU - Anna O. Ivanova
TI - Precise Upper Bound for the Strong Edge Chromatic Number of Sparse Planar Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2013
VL - 33
IS - 4
SP - 759
EP - 770
AB - 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 ∆.
LA - eng
KW - planar graph; edge coloring; 2-distance coloring; strong edgecoloring; strong edge coloring
UR - http://eudml.org/doc/267877
ER -

References

top
  1. [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] Zbl1029.05047
  2. [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. [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). Zbl1012.05074
  4. [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. [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). Zbl1076.05032
  6. [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] Zbl1184.05040
  7. [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] Zbl1190.05055
  8. [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] Zbl1255.05075
  9. [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] Zbl1233.05098
  10. [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). Zbl1077.05040
  11. [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). Zbl1249.05113
  12. [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). Zbl1119.05039
  13. [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] Zbl1143.05025
  14. [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] Zbl1172.05023
  15. [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] Zbl1143.05027
  16. [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] Zbl1159.05018
  17. [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] Zbl0721.05018
  18. [18] F. Havet, Choosability of the square of planar subcubic graphs with large girth, Discrete Math. 309 (2009) 3353-3563.[WoS] Zbl1213.05084
  19. [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 Zbl05284956
  20. [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/> Zbl05284956
  21. [21] P. Horák, The strong chromatic index of graphs with maximum degree four , Contemp. Methods in Graph Theory (1990) 399-403. Zbl0715.05023
  22. [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). Zbl1249.05118
  23. [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). Zbl1274.05165
  24. [24] T. Jensen and B. Toft, Graph Coloring Problems (New York: John Willey & Sons, 1995). 
  25. [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] Zbl1040.90034
  26. [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. [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] Zbl1178.05042
  28. [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. [29] V.G. Vizing, On an estimate of the chromatic index of a p-graph, Diskret. Analiz 3 (1964) 25-30 (in Russian). 
  30. [30] V.G. Vizing, Critical graphs with given chromatic index, Metody Diskret. Analiz 5 (1965) 9-17 (in Russian). 
  31. [31] G. Wegner, Graphs with given diameter and a coloring problem, Technical Report (University of Dortmund, Germany, 1977). 
  32. [32] D.B. West, Strong edge-coloring (Open Problems-Graph Theory and Combinatorics, http://www.math.uiuc.edu/west/openp/strongedge.html, 2003). 
  33. [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] Zbl0988.05042

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.