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 条
  • [21] ON EDGE COLORINGS OF 1-PLANAR GRAPHS WITHOUT 5-CYCLES WITH TWO CHORDS
    Sun, Lin
    Wu, Jianliang
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2019, 39 (02) : 301 - 312
  • [22] Compact Drawings of 1-Planar Graphs with Right-Angle Crossings and Few Bends
    Chaplick, Steven
    Lipp, Fabian
    Wolff, Alexander
    Zink, Johannes
    GRAPH DRAWING AND NETWORK VISUALIZATION, GD 2018, 2018, 11282 : 137 - 151
  • [23] On Sufficient Conditions for Planar Graphs to be 5-Flexible
    Yang, Fan
    GRAPHS AND COMBINATORICS, 2022, 38 (03)
  • [24] On Sufficient Conditions for Planar Graphs to be 5-Flexible
    Fan Yang
    Graphs and Combinatorics, 2022, 38
  • [25] Compact drawings of 1-planar graphs with right-angle crossings and few bends
    Chaplick, Steven
    Lipp, Fabian
    Wolff, Alexander
    Zink, Johannes
    COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2019, 84 : 50 - 68
  • [26] A Sufficient Condition for an IC-Planar Graph to be Class 1
    Duan, Yuanyuan
    Song, Wenyao
    GRAPHS AND COMBINATORICS, 2021, 37 (06) : 2305 - 2313
  • [27] A Sufficient Condition for an IC-Planar Graph to be Class 1
    Yuanyuan Duan
    Wenyao Song
    Graphs and Combinatorics, 2021, 37 : 2305 - 2313
  • [28] A new sufficient condition for graphs of f-class 1
    Zhang, Xia
    Liu, Guizhen
    Cai, Jiansheng
    Hou, Jianfeng
    ARS COMBINATORIA, 2010, 97A : 403 - 412
  • [29] Some sufficient conditions for a graph to be of Cf 1
    Zhang, X
    Liu, GZ
    APPLIED MATHEMATICS LETTERS, 2006, 19 (01) : 38 - 44
  • [30] Edge coloring of 1-planar graphs without intersecting triangles and chordal 5-cycles
    Jin, Jing
    Xu, Baogang
    ARS COMBINATORIA, 2017, 135 : 71 - 81
12345