L(2, 1)-Labelings of Some Families of Oriented Planar Graphs
Sagnik Sen
Discussiones Mathematicae Graph Theory, Tome 34 (2014), p. 31-48 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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.

Publié le : 2014-01-01
EUDML-ID : urn:eudml:doc:267731 
@article{bwmeta1.element.doi-10_7151_dmgt_1713,
     author = {Sagnik Sen},
     title = {L(2, 1)-Labelings of Some Families of Oriented Planar Graphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {34},
     year = {2014},
     pages = {31-48},
     zbl = {1292.05228},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1713}
}

Sagnik Sen. L(2, 1)-Labelings of Some Families of Oriented Planar Graphs. Discussiones Mathematicae Graph Theory, Tome 34 (2014) pp. 31-48. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1713/

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

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

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

[4] J.P. Georges and D.W. Mauro, Generalized vertex labelings with a condition at distance two, Congr. Numer. (1995) 141-160.[WoS] | Zbl 0904.05077

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

[8] T.H. Marshall, Homomorphism bounds for oriented planar graphs, J. Graph Theory 55 (2007) 175-190. doi:10.1002/jgt.20233[WoS][Crossref] | Zbl 1120.05039

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

[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). | Zbl 0712.68054