Geodesic
On (p, 1)-Total Labelling of Some 1-Planar Graphs
Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 2, pp. 531-558.

Voir la notice de l'article provenant de la source Library of Science

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 (p ≥ 2) of every 1-planar graph G is at most Δ(G) + 2p − 2 provided that Δ (G) ≥ 6p + 7 or Δ (G) ≥ 4p + 6 and G is triangle-free.
Keywords: 1-planar graph, total coloring, structural theorem, (p, 1)-total labelling 
@article{DMGT_2021_41_2_a12,
     author = {Niu, Bei and Zhang, Xin},
     title = {On (p, {1)-Total} {Labelling} of {Some} {1-Planar} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {531--558},
     publisher = {mathdoc},
     volume = {41},
     number = {2},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2021_41_2_a12/}
}
TY  - JOUR
AU  - Niu, Bei
AU  - Zhang, Xin
TI  - On (p, 1)-Total Labelling of Some 1-Planar Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2021
SP  - 531
EP  - 558
VL  - 41
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2021_41_2_a12/
LA  - en
ID  - DMGT_2021_41_2_a12
ER  - 
%0 Journal Article
%A Niu, Bei
%A Zhang, Xin
%T On (p, 1)-Total Labelling of Some 1-Planar Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2021
%P 531-558
%V 41
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2021_41_2_a12/
%G en
%F DMGT_2021_41_2_a12
Niu, Bei; Zhang, Xin. On (p, 1)-Total Labelling of Some 1-Planar Graphs. Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 2, pp. 531-558. http://geodesic.mathdoc.fr/item/DMGT_2021_41_2_a12/

[1] F. Bazzaro, M. Montassier and A. Raspaud, (d, 1)-total labelling of planar graphs with large girth and high maximum degree, Discrete Math. 307 (2007) 2141–2151. doi:10.1016/j.disc.2005.12.059

[2] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (North-Holland, New York, 1976).

[3] O.V. Borodin, A new proof of the 6 color theorem, J. Graph Theory 19 (1995) 507–521. doi:10.1002/jgt.3190190406

[4] O.V. Borodin, Solution of Ringel’s problems on the vertex-face coloring of plane graphs and on the coloring of 1 -planar graphs, Diskret. Analiz 41 (1984) 12–26.

[5] J.R. Griggs and R.K. Yeh, Labeling graphs with a condition at distance two, SIAM J. Discrete Math. 5 (1992) 586–595. doi:10.1137/0405048

[6] I. Fabrici and T. Madaras, The structure of 1 -planar graphs, Discrete Math. 307 (2007) 854–865. doi:10.1016/j.disc.2005.11.056

[7] F. Havet, (d, 1)-total labelling of graphs, in: Workshop on Graphs and Algorithms (Dijon, France, 2003).

[8] F. Havet and M.-L. Yu, (d, 1)-total labelling of graphs, Technical Report, 4650 (INRIA, 2002).

[9] F. Havet and M.-L. Yu, (p, 1)-total labelling of graphs, Discrete Math. 308 (2008) 496–513. doi:10.1016/j.disc.2007.03.034

[10] L. Kowalik, J.-S. Sereni and R. Škrekovski, Total-coloring of plane graphs with maximum degree nine, SIAM J. Discrete Math. 22 (2008) 1462–1479. doi:10.1137/070688389

[11] S.G. Kobourov, G. Liotta and F. Montecchiani, An annotated bibliography on 1-planarity, Comput. Sci. Rev. 25 (2017) 49–67. doi:10.1016/j.cosrev.2017.06.002

[12] M. Montassier and A. Raspaud, (d, 1)-total labeling of graphs with a given maximum average degree, J. Graph Theory 51 (2006) 93–109. doi:10.1002/jgt.20124

[13] G. Ringel, Ein Sechsfarbenproblem auf der Kugel, Abh. Math. Semin. Univ. Hambg. 29 (1965) 107–117. doi:10.1007/BF02996313

[14] L. Sun and J.-L. Wu, On (p, 1)-total labelling of planar graphs, J. Comb. Optim. 33 (2017) 317–325. doi:10.1007/s10878-015-9958-7

[15] J.-L. Wu and P. Wang, List-edge and list-total colorings of graphs embedded on hyperbolic surfaces, Discrete Math. 308 (2008) 6210–6215. doi:10.1016/j.disc.2007.11.044

[16] R.K. Yeh, Labelling Graphs with a Condition at Distance Two, Ph.D. Thesis (Dept. of Math., Univ. of South Carolina, Columbia, SC, USA, 1990).

[17] Y. Yu, X. Zhang, G. Wang, G. Liu and J. Li, (2, 1)-total labelling of planar graphs with large maximum degree, J. Discrete Math. Sci. Cryptogr. 20 (2017) 1625–1636. doi:10.1080/09720529.2016.1139850

[18] X. Zhang, B. Niu and J. Yu, A structure of 1-planar graph and its applications to coloring problems, Graphs Combin. 35 (2019) 677–688. doi:10.1007/s00373-019-02027-0

[19] X. Zhang and J.-L. Wu, On edge colorings of 1-planar graphs, Inform. Process. Lett. 111 (2011) 124–128. doi:10.1016/j.ipl.2010.11.001

[20] X. Zhang, J.-L. Wu and G. Liu, List edge and list total coloring of 1-planar graphs, Front. Math. China 7 (2012) 1005–1018. doi:10.1007/s11464-012-0184-7

[21] X. Zhang, Y. Yu and G. Liu, On (p, 1)-total labelling of 1-planar graphs, Cent. Eur. J. Math. 9 (2011) 1424–1434. doi:10.2478/s11533-011-0092-1