On (p, 1)-total labelling of 1-planar graphs

Xin Zhang; Yong Yu; Guizhen Liu

Open Mathematics (2011)

  • Volume: 9, Issue: 6, page 1424-1434
  • ISSN: 2391-5455

Abstract

top
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.

How to cite

top

Xin Zhang, Yong Yu, and Guizhen Liu. "On (p, 1)-total labelling of 1-planar graphs." Open Mathematics 9.6 (2011): 1424-1434. <http://eudml.org/doc/269282>.

@article{XinZhang2011,
abstract = {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.},
author = {Xin Zhang, Yong Yu, Guizhen Liu},
journal = {Open Mathematics},
keywords = {1-planar graph; Alternating subgraph; Master; Total labelling; Discharging; frequency assignment},
language = {eng},
number = {6},
pages = {1424-1434},
title = {On (p, 1)-total labelling of 1-planar graphs},
url = {http://eudml.org/doc/269282},
volume = {9},
year = {2011},
}

TY - JOUR
AU - Xin Zhang
AU - Yong Yu
AU - Guizhen Liu
TI - On (p, 1)-total labelling of 1-planar graphs
JO - Open Mathematics
PY - 2011
VL - 9
IS - 6
SP - 1424
EP - 1434
AB - 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.
LA - eng
KW - 1-planar graph; Alternating subgraph; Master; Total labelling; Discharging; frequency assignment
UR - http://eudml.org/doc/269282
ER -

References

top
  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 Zbl1106.05038
  2. [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 Zbl1120.05076
  3. [3] Bondy J.A., Murty U.S.R., Graph Theory with Applications, American Elsevier, New York, 1976 Zbl1226.05083
  4. [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) Zbl0565.05027
  5. [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 Zbl0653.05029
  6. [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 Zbl0826.05027
  7. [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) Zbl1249.05203
  8. [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 Zbl0996.05053
  9. [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 Zbl0883.05053
  10. [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 Zbl0876.05032
  11. [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 Zbl0886.05065
  12. [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. [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 Zbl1129.05041
  14. [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 Zbl1111.05026
  15. [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 Zbl1326.05131
  16. [16] Havet F., (d, 1)-total labelling of graphs, In: Workshop on Graphs and Algorithms, Dijon, 2003 
  17. [17] Havet F., Yu M.-L., (d, 1)-total labelling of graphs, INRIA, 2002, Technical Report #4650 
  18. [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 Zbl1137.05062
  19. [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 Zbl1194.05025
  20. [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 Zbl1237.05053
  21. [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 Zbl1184.05046
  22. [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 Zbl1084.05061
  23. [23] Ringel G., Ein Sechsfarbenproblem auf der Kugel, Abh. Math. Semin. Univ. Hamburg, 1965, 29, 107–117 http://dx.doi.org/10.1007/BF02996313 Zbl0132.20701
  24. [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. [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 Zbl1155.05016
  26. [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 Zbl0844.05084
  27. [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 Zbl1189.05067
  28. [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 Zbl1094.05047
  29. [29] Zhang X., Liu G., On edge colorings of 1-planar graphs without chordal 5-cycles, Ars Combin. (in press) Zbl1274.05186
  30. [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 Zbl1239.05078
  31. [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) Zbl1240.05125
  32. [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. [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) Zbl1252.05047
  34. [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 Zbl1259.05050
  35. [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 Zbl1254.05050

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.