Strong Chromatic Index Of Planar Graphs With Large Girth

Gerard Jennhwa Chang; Mickael Montassier; Arnaud Pêche; André Raspaud

Discussiones Mathematicae Graph Theory (2014)

  • Volume: 34, Issue: 4, page 723-733
  • ISSN: 2083-5892

Abstract

top
Let Δ ≥ 4 be an integer. In this note, we prove that every planar graph with maximum degree Δ and girth at least 1 Δ+46 is strong (2Δ−1)-edgecolorable, that is best possible (in terms of number of colors) as soon as G contains two adjacent vertices of degree Δ. This improves [6] when Δ ≥ 6.

How to cite

top

Gerard Jennhwa Chang, et al. "Strong Chromatic Index Of Planar Graphs With Large Girth." Discussiones Mathematicae Graph Theory 34.4 (2014): 723-733. <http://eudml.org/doc/269822>.

@article{GerardJennhwaChang2014,
abstract = {Let Δ ≥ 4 be an integer. In this note, we prove that every planar graph with maximum degree Δ and girth at least 1 Δ+46 is strong (2Δ−1)-edgecolorable, that is best possible (in terms of number of colors) as soon as G contains two adjacent vertices of degree Δ. This improves [6] when Δ ≥ 6.},
author = {Gerard Jennhwa Chang, Mickael Montassier, Arnaud Pêche, André Raspaud},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {planar graphs; edge coloring; 2-distance coloring; strong edgecoloring.; 2-distance-coloring; strong edge coloring},
language = {eng},
number = {4},
pages = {723-733},
title = {Strong Chromatic Index Of Planar Graphs With Large Girth},
url = {http://eudml.org/doc/269822},
volume = {34},
year = {2014},
}

TY - JOUR
AU - Gerard Jennhwa Chang
AU - Mickael Montassier
AU - Arnaud Pêche
AU - André Raspaud
TI - Strong Chromatic Index Of Planar Graphs With Large Girth
JO - Discussiones Mathematicae Graph Theory
PY - 2014
VL - 34
IS - 4
SP - 723
EP - 733
AB - Let Δ ≥ 4 be an integer. In this note, we prove that every planar graph with maximum degree Δ and girth at least 1 Δ+46 is strong (2Δ−1)-edgecolorable, that is best possible (in terms of number of colors) as soon as G contains two adjacent vertices of degree Δ. This improves [6] when Δ ≥ 6.
LA - eng
KW - planar graphs; edge coloring; 2-distance coloring; strong edgecoloring.; 2-distance-coloring; strong edge coloring
UR - http://eudml.org/doc/269822
ER -

References

top
  1. [1] 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 
  2. [2] K. Appel and W. Haken, Every planar map is four colorable. Part I. Discharging, Illinois J. Math. 21 (1977) 429-490. Zbl0387.05009
  3. [3] K. Appel and W. Haken, Every planar map is four colorable. Part II. Reducibility, Illinois J. Math. 21 (1977) 491-567. Zbl0387.05010
  4. [4] C.L. Barrett, G. Istrate, V.S.A. Kumar, M.V. Marathe, S. Thite, and S. Thulasidasan, Strong edge coloring for channel assignment in wireless radio networks, in: Proc. of the 4th Annual IEEE International Conference on Pervasive Computing and Communications Workshops (2006) 106-110. 
  5. [5] N. Biggs, Some odd graph theory, Annals New York Academy of Sciences 319 (1979) 71-81. Zbl0479.05039
  6. [6] O.V. Borodin and A.O. Ivanova, Precise upper bound for the strong edge chromatic number of sparse planar graphs, Discuss. Math. Graph Theory 33 (2013) 759-770. doi:10.7151/dmgt.1708 Zbl1301.05118
  7. [7] 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 Zbl1143.05025
  8. [8] P. Erdős, Problems and results in combinatorial analysis and graph theory, Discrete Math. 72 (1988) 81-92. doi:10.1016/0012-365X(88)90196-3 
  9. [9] P. Erdős and J. Nešetřil, Problem, in: Irregularities of Partitions, G. Hal´asz and V.T. S´os (Eds.) (Springer, Berlin, 1989) 162-163. 
  10. [10] R.J. Faudree, A. Gyárfas, R.H. Schelp and Zs. Tuza, The strong chromatic index of graphs, Ars Combin. 29B (1990) 205-211. Zbl0721.05018
  11. [11] J.L. Fouquet and J.L. Jolivet, Strong edge-coloring of graphs and applications to multi-k-gons, Ars Combin. 16 (1983) 141-150. Zbl0536.05027
  12. [12] J.L. Fouquet and J.L. Jolivet, Strong edge-coloring of cubic planar graphs, Progress in Graph Theory (Waterloo 1982), (1984) 247-264. 
  13. [13] H. Grötzsch, Ein Dreifarbensatz für Dreikreisfreie Netze auf der Kugel , Math.-Nat. Reihe 8 (1959) 109-120. 
  14. [14] H. Hocquard, P. Ochem and P. Valicov, Strong edge coloring and induced matchings, LaBRI Research Report, 2011. http://hal.archives-ouvertes.fr/hal-00609454_v1/ Zbl1284.68281
  15. [15] P. Horák, H. Qing, and W.T. Trotter, Induced matchings in cubic graphs, J. Graph Theory 17 (1993) 151-160. doi:10.1002/jgt.3190170204 Zbl0787.05038
  16. [16] M. Mahdian, The strong chromatic index of graphs, Master Thesis (University of Toronto, Canada, 2000). Zbl0961.05022
  17. [17] M. Molloy and B. Reed, A bound on the strong chromatic index of a graph, J. Combin. Theory (B) 69 (1997) 103-109. doi:10.1006/jctb.1997.1724 
  18. [18] T. Nandagopal, T. Kim, X. Gao and V. Bharghavan, Achieving MAC layer fairness in wireless packet networks, in: Proc. 6th ACM Conf. on Mobile Computing and Networking (2000) 87-98. 
  19. [19] J. Nešetřil, A. Raspaud and A. Sopena, Colorings and girth of oriented planar graphs, Discrete Math. 165-166 (1997) 519-530. doi:10.1016/S0012-365X(96)00198-7 Zbl0873.05042
  20. [20] S. Ramanathan, A unified framework and algorithm for (T/F/C) DMA channel assignment in wireless networks, in: Proc. IEEE INFOCOM’97 (1997) 900-907. doi:10.1109/INFCOM.1997.644573 
  21. [21] S. Ramanathan and E.L. Lloyd, Scheduling algorithms for multi-hop radio networks, in: IEEE/ACM Trans. Networking 2 (1993) 166-177. doi:10.1109/90.222924 
  22. [22] D.P. Sanders and Y. Zhao, Planar graphs of maximum degree seven are Class 1, J. Combin. Theory (B) 83 (2001) 201-212. doi:1006/jctb.2001.2047 Zbl1024.05031
  23. [23] V.G. Vizing, On an estimate of the chromatic class of a p-graph, Diskret. Analiz. 3 (1964) 25-30. 

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.