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

• Autorzy: Oleg V. Borodin , Anna O. Ivanova
• Języki publikacji: EN

Abstrakty

EN

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

Słowa kluczowe

EN

planar graph; edge coloring; 2-distance coloring; strong edgecoloring

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2013
• Tom: 33
• Numer: 4
• Strony: 759-770

Daty

wydano

2013-09-01

online

2013-10-15

Twórcy

autor

Oleg V. Borodin

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

autor

Anna O. Ivanova

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

Bibliografia

• [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]
• [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).
• [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[Crossref]
• [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]
• [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]
• [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]
• [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[Crossref]
• [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]
• [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]
• [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]
• [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]
• [18] F. Havet, Choosability of the square of planar subcubic graphs with large girth, Discrete Math. 309 (2009) 3353-3563.[WoS]
• [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é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[Crossref]
• [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]
• [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]

Identyfikatory

DOI

10.7151/dmgt.1708