Strong Chromatic Index Of Planar Graphs With Large Girth

• Autorzy: Gerard Jennhwa Chang , Mickael Montassier , Arnaud Pêche , André Raspaud
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

planar graphs; edge coloring; 2-distance coloring; strong edgecoloring.

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2014
• Tom: 34
• Numer: 4
• Strony: 723-733

Daty

wydano

2014-11-01

otrzymano

2013-04-05

poprawiono

2013-10-30

zaakceptowano

2013-10-30

online

2014-11-15

Twórcy

autor

Gerard Jennhwa Chang

• Department of Mathematics/Taida Institute for Mathematical Sciences National Taiwan University, Taipei 10617, Taiwan/National Center for Theoretical Sciences, Taipei Office, Taiwan

autor

Mickael Montassier

• Universit Montpellier 2, CNRS-LIRMM, UMR5506 161 rue Ada, 34095 Montpellier Cedex 5, France

autor

Arnaud Pêche

• LaBRI - University of Bordeaux 351 cours de la Liberation, 33405 Talence Cedex, France

autor

André Raspaud

• LaBRI - University of Bordeaux 351 cours de la Liberation, 33405 Talence Cedex, France

Bibliografia

• [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´asz 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.

Identyfikatory

DOI

10.7151/dmgt.1763