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

被引:0
|
作者
Sun, Lin [1 ,2 ]
Cai, Hua [1 ,2 ]
机构
[1] Changji Univ, Dept Math, Changji 831100, Peoples R China
[2] Shandong Univ, Sch Math, Jinan 250100, Peoples R China
关键词
1-planar graph; (p; 1)-total labelling; minimal counterexample; discharging method; TOTAL COLORINGS; EDGE COLORINGS; PLANAR GRAPHS;
D O I
暂无
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
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. A k-(p, 1)-total labelling of a graph G is a function f from V(G) boolean OR E(G) to the color set {0,1, ..., k} such that vertical bar f(u) - f(v)vertical bar >= 1 if uv epsilon E(G), vertical bar f(e(1)) - f(e(2))vertical bar >= 1 if e(1) and e(2) are two adjacent edges in G and vertical bar f(u) - f(e)vertical bar >= p if the vertex u is incident to the edge e. The minimum kappa such that G has a k-(p, 1)-total labelling, denoted by lambda(T)(p)(G), is called the (p, 1)-total labelling number of G. In this paper, we prove that, if a 1-planar graph G satisfies that maximum degree Delta(G) >= 7p + 1 and no adjacent triangles in G or maximum degree Delta(G) >= 6p + 3 and no intersecting triangles in G, then lambda(T)(p)(G) <= Delta + 2p - 2, p >= 2.
引用
收藏
页码:87 / 96
页数:10
相关论文
共 50 条
  • [41] Adjacent vertex distinguishing edge choosability of 1-planar graphs with maximum degree at least 23
    Sun, Lin
    Yu, Guanglong
    Li, Xin
    DISCRETE APPLIED MATHEMATICS, 2023, 337 : 257 - 271
  • [42] Acyclic Edge Coloring of 1-planar Graphs without 4-cycles
    Wang, Wei-fan
    Wang, Yi-qiao
    Yang, Wan-shun
    ACTA MATHEMATICAE APPLICATAE SINICA-ENGLISH SERIES, 2024, 40 (01): : 35 - 44
  • [43] Drawing Subcubic 1-Planar Graphs with Few Bends, Few Slopes, and Large Angles
    Kindermann, Philipp
    Montecchiani, Fabrizio
    Schlipf, Lena
    Schulz, Andre
    GRAPH DRAWING AND NETWORK VISUALIZATION, GD 2018, 2018, 11282 : 152 - 166
  • [44] On edge colorings of 1-planar graphs with 6-cycles having at most three chords
    Sun, Lin
    Wu, Jian-Liang
    Cai, Hua
    Luo, ZhaoYang
    INTERNATIONAL JOURNAL OF APPLIED MATHEMATICS & STATISTICS, 2015, 53 (01): : 50 - 58
  • [45] Edge coloring of 1-planar graphs without intersecting triangles and chordal 5-cycles
    Jin, Jing
    Xu, Baogang
    ARS COMBINATORIA, 2017, 135 : 71 - 81
  • [46] A totally (Δ + 1)-colorable 1-planar graph with girth at least five
    Lin Sun
    Jian Liang Wu
    Hua Cai
    Acta Mathematica Sinica, English Series, 2016, 32 : 1337 - 1349
  • [47] 1-planar Graphs without 4-cycles or 5-cycles are 5-colorable
    Song, Li-li
    Sun, Lei
    ACTA MATHEMATICAE APPLICATAE SINICA-ENGLISH SERIES, 2022, 38 (01): : 169 - 177
  • [48] A Totally(Δ+1)-colorable 1-planar Graph with Girth at Least Five
    Lin SUN
    Jian Liang WU
    Hua CAI
    Acta Mathematica Sinica,English Series, 2016, 32 (11) : 1337 - 1349
  • [49] The (d, 1)-total labelling of square of cycles and their Cartesian products with bipartite graphs
    Zuo, Liancui
    Bai, Dan
    Shang, Chunhong
    ARS COMBINATORIA, 2019, 143 : 227 - 236
  • [50] Adjacency Labelling for Planar Graphs (and Beyond)
    Dujmovic, Vida
    Esperet, Louis
    Gavoille, Cyril
    Joret, Gwenael
    Micek, Piotr
    Morin, Pat
    JOURNAL OF THE ACM, 2021, 68 (06)