L(2, 1)-Labelings of Some Families of Oriented Planar Graphs

• Autorzy: Sagnik Sen
• Języki publikacji: EN

Abstrakty

EN

In this paper we determine, or give lower and upper bounds on, the 2-dipath and oriented L(2, 1)-span of the family of planar graphs, planar graphs with girth 5, 11, 16, partial k-trees, outerplanar graphs and cacti.

Słowa kluczowe

EN

2-dipath L(2; 1)-labeling; oriented L(2; 1)-labeling; homomorphism; planar graph; girth; partial k-tree; outerplanar graph; cactus

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2014
• Tom: 34
• Numer: 1
• Strony: 31-48

Daty

wydano

2014-02-01

online

2014-02-14

Twórcy

autor

Sagnik Sen

• Univ. Bordeaux, LaBRI, UMR5800, F-33400 Talence, France CNRS, LaBRI, UMR5800, F-33400 Talence, France

Bibliografia

• [1] K.I. Aardal, S.P.M. van Hoesel, A.M.C.A. Koster, C. Mannino and A. Sassano, Models and solution techniques for frequency assignment problems, Ann. Oper. Res. 153 (2007) 79-129. doi:10.1007/s10479-007-0178-0[WoS][Crossref]
• [2] T. Calamoneri and B. Sinaimeri, L(2, 1)-labeling of oriented planar graphs, Discrete Appl. Math. 161 (2013) 1719-1725. doi:10.1016/j.dam.2012.07.009[Crossref][WoS]
• [3] G.J. Chang, J.J Chen, D. Kuo and S.C. Liaw, Distance-two labelings of digraphs, Discrete Appl. Math. 155 (2007) 1007-1013. doi:10.1016/j.dam.2006.11.001[Crossref][WoS]
• [4] J.P. Georges and D.W. Mauro, Generalized vertex labelings with a condition at distance two, Congr. Numer. (1995) 141-160.[WoS]
• [5] D. Gonçalves, M.A. Shalu and A. Raspaud, On oriented labelling parameters, Formal Models, Languages and Applications 66 (2006) 34-45. doi:10.1142/9789812773036 0003[Crossref]
• [6] J.R. Griggs and R.K. Yeh, Labelling graphs with a condition at distance 2, SIAM J. Discrete Math. 5 (1992) 586-595. doi:10.1137/0405048[Crossref]
• [7] P. Hell, A.V. Kostochka, A. Raspaud and E. Sopena, On nice graphs, Discrete Math. 234 (2001) 39-51. doi:10.1016/S0012-365X(00)00190-4[Crossref]
• [8] T.H. Marshall, Homomorphism bounds for oriented planar graphs, J. Graph Theory 55 (2007) 175-190. doi:10.1002/jgt.20233[WoS][Crossref]
• [9] A. Pinlou, An oriented coloring of planar graphs with girth at least five, Discrete Math. 309 (2009) 2108-2118. doi:10.1016/j.disc.2008.04.030[Crossref]
• [10] A. Raspaud and E. Sopena, Good and semi-strong colorings of oriented planar graphs, Inform. Process. Lett. 51 (1994) 171-174. doi:10.1016/0020-0190(94)00088-3[Crossref]
• [11] E. Sopena, The chromatic number of oriented graphs, J. Graph Theory 25 (1997) 191-205. doi:10.1002/(SICI)1097-0118(199707)25:3h191::AID-JGT3i3.0.CO;2-G[Crossref]
• [12] E. Sopena, Oriented graph coloring, Discrete Math. 229 (2001) 359-369. doi:10.1016/S0012-365X(00)00216-8[Crossref]
• [13] E. Sopena, There exist oriented planar graphs with oriented chromatic number at least sixteen, Inform. Process. Lett. 81 (2002) 309-312. doi:10.1016/S0020-0190(01)00246-0[Crossref]
• [14] J. van Leeuwen, Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity (Elsevier and MIT Press, 1990).

Identyfikatory

DOI

10.7151/dmgt.1713