### 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

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.

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