Some sufficient conditions for 1-planar graphs to be Class 1

被引：1
|
作者：
Zhang, Wenwen [1 ]
Wu, Jian-Liang [1 ]
机构：
[1] Shandong Univ, Sch Math, Jinan 250100, Peoples R China
来源：
THEORETICAL COMPUTER SCIENCE | 2015年 / 566卷
关键词：
1-Planar graphs; Edge coloring; Cycle; EDGE COLORINGS; PLANAR GRAPH;
D O I：
10.1016/j.tcs.2014.11.031
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
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. Let G be a 1-planar graph with maximum degree Delta(G). In this paper, it is shown that chi' (G) = Delta(G) if (1) Delta(G) >= 9 and G contains no adjacent chordal 5-cycles, or (2) Delta(G) >= 8 and G contains no adjacent 4-cycles or no 5-cycles. (C) 2014 Elsevier B.V. All rights reserved.
引用
收藏
页码：50 / 58
页数：9
相关论文
共 50 条
  • [1] Some sufficient conditions for a planar graph of maximum degree six to be Class 1
    Bu, Yuehua
    Wang, Weifan
    DISCRETE MATHEMATICS, 2006, 306 (13) : 1440 - 1445
  • [2] On total colorings of 1-planar graphs
    Zhang, Xin
    Hou, Jianfeng
    Liu, Guizhen
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2015, 30 (01) : 160 - 173
  • [3] On edge colorings of 1-planar graphs
    Zhang, Xin
    Wu, Jian-Liang
    INFORMATION PROCESSING LETTERS, 2011, 111 (03) : 124 - 128
  • [4] On drawings and decompositions of 1-planar graphs
    Czap, Julius
    Hudak, David
    ELECTRONIC JOURNAL OF COMBINATORICS, 2013, 20 (02):
  • [5] On list (p, 1)-total labellings of special planar graphs and 1-planar graphs
    Lin Sun
    Guanglong Yu
    Jianliang Wu
    Journal of Combinatorial Optimization, 2024, 47
  • [6] On list (p, 1)-total labellings of special planar graphs and 1-planar graphs
    Sun, Lin
    Yu, Guanglong
    Wu, Jianliang
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2024, 47 (03)
  • [7] A note on total colorings of 1-planar graphs
    Czap, Julius
    INFORMATION PROCESSING LETTERS, 2013, 113 (14-16) : 516 - 517
  • [8] NOTE ON IMPROPER COLORING OF 1-PLANAR GRAPHS
    Chu, Yanan
    Sun, Lei
    Yue, Jun
    CZECHOSLOVAK MATHEMATICAL JOURNAL, 2019, 69 (04) : 955 - 968
  • [9] On edge colorings of 1-planar graphs without adjacent triangles
    Zhang, Xin
    Liu, Guizhen
    INFORMATION PROCESSING LETTERS, 2012, 112 (04) : 138 - 142
  • [10] On (p, 1)-total labelling of special 1-planar graphs
    Sun, Lin
    Cai, Hua
    ARS COMBINATORIA, 2015, 123 : 87 - 96
12345