• •

### 不含3圈和4圈的1-平面图是5-可染的

1. 山东师范大学数学与统计学院, 山东 济南 250014
• 收稿日期:2016-04-18 出版日期:2017-04-20 发布日期:2017-04-11
• 通讯作者: 孙磊(1971— ),女,博士,副教授,研究方向为图论.E-mail:lsun89@163.com E-mail:1017155867@qq.com
• 作者简介:王晔(1992— ),女,研究生,研究方向图论与组合优化.E-mail:1017155867@qq.com
• 基金资助:
国家自然科学基金(11626148);山东省自然科学基金教育厅联合基金项目资助(ZR2014JL001)

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

• 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] 张佳丽,苗连英,宋文耀. 最大度为8不含相邻4-圈的1-平面图边色数[J]. 山东大学学报（理学版）, 2014, 49(04): 18-23. [2] 张欣,刘桂真,吴建良. 不含3-圈的1-平面图的边染色[J]. J4, 2010, 45(6): 15-17.
Viewed
Full text

Abstract

Cited

Shared
Discussed