PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2014 | 34 | 4 | 723-733
Tytuł artykułu

Strong Chromatic Index Of Planar Graphs With Large Girth

Treść / Zawartość
Warianty tytułu
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.
Wydawca
Rocznik
Tom
34
Numer
4
Strony
723-733
Opis fizyczny
Daty
wydano
2014-11-01
otrzymano
2013-04-05
poprawiono
2013-10-30
zaakceptowano
2013-10-30
online
2014-11-15
Twórcy
  • Department of Mathematics/Taida Institute for Mathematical Sciences National Taiwan University, Taipei 10617, Taiwan/National Center for Theoretical Sciences, Taipei Office, Taiwan
  • Universit Montpellier 2, CNRS-LIRMM, UMR5506 161 rue Ada, 34095 Montpellier Cedex 5, France
  • LaBRI - University of Bordeaux 351 cours de la Liberation, 33405 Talence Cedex, France
  • LaBRI - University of Bordeaux 351 cours de la Liberation, 33405 Talence Cedex, France, raspaud@labri.fr
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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1763
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.