JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2017, Vol. 52 ›› Issue (4): 34-39.doi: 10.6040/j.issn.1671-9352.0.2016.171

Previous Articles     Next Articles

Every 1-planar graph without cycles of length 3 or 4 is 5-colorable

WANG Ye, SUN Lei*   

  1. School of Mathematics and Statistics, Shandong Normal University, Jinan 250014, Shandong, China
  • Received:2016-04-18 Online:2017-04-20 Published:2017-04-11

PDF (PC)

741

Abstract: A graph G is called 1-planar graph if it can be drawn on the plane so that each edge is crossed by at most one other edge. A propervertexcoloring of G is an assignment φ of integer to the vertex of G such that φ(u)≠φ(v)if the vertex u and v adjacent in G. A k-coloring is a proper vertex coloring using k colors at least. The theorem that every 1-planar graph without cycles of length 3 or 4 is 5-colorable was given by the Discharging Method.

Key words: cross vertices, cross faces, k-colorable, 1-planar graph

CLC Number: 

  • O157.5
[1] APPLE K, HAKEN W. Every planar map is four colorable part I[J]. Discharging Illionois J Math, 1977, 21:429-490.
[2] BORDIN O V. Solution of Ringels problems on the vertex-face coloring of plane graphs and on the coloring of 1-planar graphs(in Russian)[J]. Metody Diskret Analiz, 1984, 108(41):12-26.
[3] FABIRIC I, MADARAS T. The structure of 1-planar graphs[J]. Discrete Math, 2007, 307:854-865.
[4] 张欣, 吴建良. 1-平面图的结构性质及其在无圈边染色上的应用[J]. 中国科学(数学), 2010, 40(10):1025-1032. ZHANG Xin, WU Jianliang. Structural properties of 1-planar graphs and an application to acyclic edge coloring[J]. Science China Press, 2010, 40(10): 1025-1032.
[5] ZHANG X, WU J L. On edge coloring of 1-planar graphs[J]. Inform Process lett, 2011, 111(1): 124-128.
[6] ZHANG X, LIU G. On edge colorings of 1-planar graphs without chordal 5-cycles[J]. Ars Combinatoria-Waterloo then Winnipeg, 2012, 104.
[7] BOLLOBAS B. Modern Graph Theory[M]. New York: Springer-Verlag, 2008.
[8] ZHANG X, LIU G. On edge colorings of 1-planar graphs without adjacent triangles[J]. Information Processing Letters, 2012, 112(4):138-142.
[1] ZHANG Jia-li, MIAO Lian-ying, SONG Wen-yao. Edge colorings of 1-planar graphs for maximum degree eight #br# without adjacent 4-cycles [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(04): 18-23.
[2] ZHANG Xin, LIU Gui-zhen, WU Jian-liang. Edge coloring of triangle-free 1-planar graphs [J]. J4, 2010, 45(6): 15-17.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd