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

• Autorzy: Xin Zhang , Yong Yu , Guizhen Liu
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

1-planar graph; Alternating subgraph; Master; Total labelling; Discharging

Kategorie tematyczne

• 05C15: Coloring of graphs and hypergraphs
• 05C10: Planar graphs; geometric and topological aspects of graph theory

• Wydawca: De Gruyter Open
• Czasopismo: Open Mathematics
• Rocznik: 2011
• Tom: 9
• Numer: 6
• Strony: 1424-1434

Daty

wydano

2011-12-01

online

2011-09-23

Twórcy

autor

Xin Zhang

• Shandong University

autor

Yong Yu

• Shandong University

autor

Guizhen Liu

• Shandong University

Bibliografia

• [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
• [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
• [3] Bondy J.A., Murty U.S.R., Graph Theory with Applications, American Elsevier, New York, 1976
• [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)
• [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
• [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
• [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)
• [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
• [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
• [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
• [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
• [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
• [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
• [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
• [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
• [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
• [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
• [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
• [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
• [23] Ringel G., Ein Sechsfarbenproblem auf der Kugel, Abh. Math. Semin. Univ. Hamburg, 1965, 29, 107–117 http://dx.doi.org/10.1007/BF02996313
• [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
• [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
• [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
• [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
• [29] Zhang X., Liu G., On edge colorings of 1-planar graphs without chordal 5-cycles, Ars Combin. (in press)
• [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
• [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)
• [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)
• [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
• [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

Identyfikatory

DOI

10.2478/s11533-011-0092-1