Geodesic
Strong chromatic index of planar graphs with large girth
Discussiones Mathematicae. Graph Theory, Tome 34 (2014) no. 4, pp. 723-733.

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

Let Δ ≥ 4 be an integer. In this note, we prove that every planar graph with maximum degree Δ and girth at least 10Δ+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.
Keywords: planar graphs, edge coloring, 2-distance coloring, strong edgecoloring 
@article{DMGT_2014_34_4_a5,
     author = {Jennhwa Chang, Gerard and Montassier, Mickael and P\^eche, Arnaud and Raspaud, Andr\'e},
     title = {Strong chromatic index of planar graphs with large girth},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {723--733},
     publisher = {mathdoc},
     volume = {34},
     number = {4},
     year = {2014},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2014_34_4_a5/}
}
TY  - JOUR
AU  - Jennhwa Chang, Gerard
AU  - Montassier, Mickael
AU  - Pêche, Arnaud
AU  - Raspaud, André
TI  - Strong chromatic index of planar graphs with large girth
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2014
SP  - 723
EP  - 733
VL  - 34
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2014_34_4_a5/
LA  - en
ID  - DMGT_2014_34_4_a5
ER  - 
%0 Journal Article
%A Jennhwa Chang, Gerard
%A Montassier, Mickael
%A Pêche, Arnaud
%A Raspaud, André
%T Strong chromatic index of planar graphs with large girth
%J Discussiones Mathematicae. Graph Theory
%D 2014
%P 723-733
%V 34
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2014_34_4_a5/
%G en
%F DMGT_2014_34_4_a5
Jennhwa Chang, Gerard; Montassier, Mickael; Pêche, Arnaud; Raspaud, André. Strong chromatic index of planar graphs with large girth. Discussiones Mathematicae. Graph Theory, Tome 34 (2014) no. 4, pp. 723-733. http://geodesic.mathdoc.fr/item/DMGT_2014_34_4_a5/

[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] K. Appel and W. Haken, Every planar map is four colorable. Part I. Discharging, Illinois J. Math. 21 (1977) 429-490.

[3] K. Appel and W. Haken, Every planar map is four colorable. Part II. Reducibility, Illinois J. Math. 21 (1977) 491-567.

[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] N. Biggs, Some odd graph theory, Annals New York Academy of Sciences 319 (1979) 71-81.

[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

[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

[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] P. Erdős and J. Nešetřil, Problem, in: Irregularities of Partitions, G. Halász and V.T. S´os (Eds.) (Springer, Berlin, 1989) 162-163.

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

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

[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] H. Grötzsch, Ein Dreifarbensatz für Dreikreisfreie Netze auf der Kugel, Math.-Nat. Reihe 8 (1959) 109-120.

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

[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

[16] M. Mahdian, The strong chromatic index of graphs, Master Thesis (University of Toronto, Canada, 2000).

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

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

[23] V.G. Vizing, On an estimate of the chromatic class of a p-graph, Diskret. Analiz. 3 (1964) 25-30.