PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Czasopismo
2011 | 9 | 6 | 1424-1434
Tytuł artykułu

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

Treść / Zawartość
Warianty tytułu
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.
Wydawca
Czasopismo
Rocznik
Tom
9
Numer
6
Strony
1424-1434
Opis fizyczny
Daty
wydano
2011-12-01
online
2011-09-23
Twórcy
autor
autor
  • Shandong University
autor
  • 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
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_2478_s11533-011-0092-1
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.