A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. In this paper, it is proved that the (p, 1)-total labelling number of every 1-planar graph G is at most Δ(G) + 2p − 2 provided that Δ(G) ≥ 8p+4 or Δ(G) ≥ 6p+2 and g(G) ≥ 4. As a consequence, the well-known (p, 1)-total labelling conjecture has been confirmed for some 1-planar graphs.
@article{bwmeta1.element.doi-10_2478_s11533-011-0092-1,
author = {Xin Zhang and Yong Yu and Guizhen Liu},
title = {On (p, 1)-total labelling of 1-planar graphs},
journal = {Open Mathematics},
volume = {9},
year = {2011},
pages = {1424-1434},
zbl = {1227.05135},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_2478_s11533-011-0092-1}
}
Xin Zhang; Yong Yu; Guizhen Liu. On (p, 1)-total labelling of 1-planar graphs. Open Mathematics, Tome 9 (2011) pp. 1424-1434. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_2478_s11533-011-0092-1/
[1] Albertson M.O., Mohar B., Coloring vertices and faces of locally planar graphs, Graphs Combin., 2006, 22(3), 289–295 http://dx.doi.org/10.1007/s00373-006-0653-4 | Zbl 1106.05038
[2] Bazzaro F., Montassier M., Raspaud A., (d, 1)-total labelling of planar graphs with large girth and high maximum degree, Discrete Math., 2007, 307(16), 2141–2151 http://dx.doi.org/10.1016/j.disc.2005.12.059 | Zbl 1120.05076
[3] Bondy J.A., Murty U.S.R., Graph Theory with Applications, American Elsevier, New York, 1976 | Zbl 1226.05083
[4] Borodin O.V., Solution of the Ringel problem on vertex-face coloring of planar graphs and coloring of 1-planar graphs, Metody Diskret. Analiz, 1984, 41, 12–26 (in Russian) | Zbl 0565.05027
[5] Borodin O.V., On the total coloring of planar graphs, J. Reine Angew. Math., 1989, 394, 180–185 http://dx.doi.org/10.1515/crll.1989.394.180 | Zbl 0653.05029
[6] Borodin O.V., A new proof of the 6 color theorem, J. Graph Theory, 1995, 19(4), 507–521 http://dx.doi.org/10.1002/jgt.3190190406 | Zbl 0826.05027
[7] Borodin O.V., Dmitriev I.G., Ivanova A.O., The height of a cycle of length 4 in 1-planar graphs with minimal degree 5 without triangles, Diskretn. Anal. Issled. Oper., 2008, 15(1), 11–16 (in Russian) | Zbl 1249.05203
[8] Borodin O.V., Kostochka A.V., Raspaud A., Sopena E., Acyclic coloring of 1-planar graphs, Discrete Appl. Math., 2001, 114(1–3), 29–41 http://dx.doi.org/10.1016/S0166-218X(00)00359-0 | Zbl 0996.05053
[9] Borodin O.V., Kostochka A.V., Woodall D.R., Total colorings of planar graphs with large maximum degree, J. Graph Theory, 1997, 26(1), 53–59 http://dx.doi.org/10.1002/(SICI)1097-0118(199709)26:1<53::AID-JGT6>3.0.CO;2-G | Zbl 0883.05053
[10] Borodin O.V., Kostochka A.V., Woodall D.R., List edge and list total colourings of multigraphs, J. Combin. Theory Ser. B, 1997, 71(2), 184–204 http://dx.doi.org/10.1006/jctb.1997.1780 | Zbl 0876.05032
[11] Borodin O.V., Kostochka A.V., Woodall D.R., Total colourings of planar graphs with large girth, European. J. Combin., 1998, 19(1), 19–24 http://dx.doi.org/10.1006/eujc.1997.0152 | Zbl 0886.05065
[12] Calamoneri T., The L(h, k)-labelling problem: a survey and annotated bibliography, Comput. J., 2006, 49(5), 585–608 http://dx.doi.org/10.1093/comjnl/bxl018
[13] Chen D., Wang W., (2, 1)-total labelling of outerplanar graphs, Discrete Appl. Math., 2007, 155(18), 2585–2593 http://dx.doi.org/10.1016/j.dam.2007.07.016 | Zbl 1129.05041
[14] Fabrici I., Madaras T., The structure of 1-planar graphs, Discrete Math., 2007, 307(7–8), 854–865 http://dx.doi.org/10.1016/j.disc.2005.11.056 | Zbl 1111.05026
[15] Hasunuma T., Ishii T., Ono H., Uno Y., The (2,1)-total labeling number of outerplanar graphs is at most Δ + 2, In: Combinatorial Algorithms, Lecture Notes in Comput. Sci., 6460, Springer, Berlin, 2011, 103–106 http://dx.doi.org/10.1007/978-3-642-19222-7_11 | Zbl 1326.05131
[16] Havet F., (d, 1)-total labelling of graphs, In: Workshop on Graphs and Algorithms, Dijon, 2003
[17] Havet F., Yu M.-L., (d, 1)-total labelling of graphs, INRIA, 2002, Technical Report #4650
[18] Havet F., Yu M.-L., (p, 1)-total labelling of graphs, Discrete Math., 2008, 308(4), 496–513 http://dx.doi.org/10.1016/j.disc.2007.03.034 | Zbl 1137.05062
[19] Hudák D., Madaras T., On local structures of 1-planar graphs of minimum degree 5 and girth 4, Discuss. Math. Graph Theory, 2009, 29(2), 385–400 | Zbl 1194.05025
[20] Hudák D., Madaras T., On local properties of 1-planar graphs with high minimum degree, Ars Math. Contemp., 2011, 4(2), 245–254 | Zbl 1237.05053
[21] Kowalik Ł., Sereni J.S., Škrekovski R., Total-coloring of plane graphs with maximum degree nine, SIAM J. Discrete Math., 2008, 22(4), 1462–1479 http://dx.doi.org/10.1137/070688389 | Zbl 1184.05046
[22] Montassier M., Raspaud A., (d; 1)-total labeling of graphs with a given maximum average degree, J. Graph Theory, 2006, 51(2), 93–109 http://dx.doi.org/10.1002/jgt.20124 | Zbl 1084.05061
[23] Ringel G., Ein Sechsfarbenproblem auf der Kugel, Abh. Math. Semin. Univ. Hamburg, 1965, 29, 107–117 http://dx.doi.org/10.1007/BF02996313 | Zbl 0132.20701
[24] Sanders D. P., Zhao Y., On total 9-coloring planar graphs of maximum degree seven, J. Graph Theory, 1999, 31(1), 67–73 http://dx.doi.org/10.1002/(SICI)1097-0118(199905)31:1<67::AID-JGT6>3.0.CO;2-C
[25] Wang W., Lih K.-W., Coupled choosability of plane graphs, J. Graph Theory, 2008, 58(1), 27–44 http://dx.doi.org/10.1002/jgt.20292 | Zbl 1155.05016
[26] Whittlesey M.A., Georges J.P., Mauro D.W., On the λ-number of Q n and related graphs, SIAM J. Discrete Math, 1995, 8(4), 499–506 http://dx.doi.org/10.1137/S0895480192242821 | Zbl 0844.05084
[27] Wu J., Wang P., List-edge and list-total colorings of graphs embedded on hyperbolic surfaces, Discrete Math., 2008, 308(24), 6210–6215 http://dx.doi.org/10.1016/j.disc.2007.11.044 | Zbl 1189.05067
[28] Yeh R.K., A survey on labeling graphs with a condition at distance two, Discrete Math., 2006, 306(12), 1217–1231 http://dx.doi.org/10.1016/j.disc.2005.11.029 | Zbl 1094.05047
[29] Zhang X., Liu G., On edge colorings of 1-planar graphs without chordal 5-cycles, Ars Combin. (in press) | Zbl 1274.05186
[30] Zhang X., Liu G., On edge colorings of 1-planar graphs without adjacent triangles, preprint available at http://xinzhang.hpage.com/get_file.php?id=1283123&vnr=529770 | Zbl 1239.05078
[31] Zhang X., Liu G, Wu J.-L., Edge coloring of triangle-free 1-planar graphs, J. Shandong Univ. Nat. Sci., 2010, 45(6), 15–17 (in Chinese) | Zbl 1240.05125
[32] Zhang X., Liu G., Wu J.-L., Structural properties of 1-planar graphs and an application to acyclic edge coloring, Scientia Sinica Mathematica, 2010, 40(10), 1025–1032 (in Chinese)
[33] Zhang X., Liu G., Wu J.-L., Light subgraphs in the family of 1-planar graphs with high minimum degree, Acta Math. Sin. (Engl. Ser.) (in press) | Zbl 1252.05047
[34] Zhang X., Wu J.-L., On edge colorings of 1-planar graphs, Inform. Process. Lett., 2011, 111(3), 124–128 http://dx.doi.org/10.1016/j.ipl.2010.11.001 | Zbl 1259.05050
[35] Zhang X., Wu J.-L., Liu G., List edge and list total coloring of 1-planar graphs, preprint available at http://xinzhang.hpage.com/get_file.php?id=1251999&vnr=768295 | Zbl 1254.05050