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

doi:10.6040/j.issn.1671-9352.0.2016.171

山东大学学报（理学版） ›› 2017, Vol. 52 ›› Issue (4): 34-39.doi: 10.6040/j.issn.1671-9352.0.2016.171

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

王晔,孙磊^*

山东师范大学数学与统计学院, 山东济南 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^*

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

摘要： 若图G能画到平面上,且允许每条边至多出现一个交叉点,则图G是1-平面图。图G的一个正常点染色是指存在一个顶点集到颜色集的映射φ:V(G)→{1,2,…,k},对于 G 中的任意两个相邻的点u和v,φ(u)≠φ(v)。图 G 的一个 k 染色是指图 G 能够正常点染色所需的色数至少为 k, 图 G 有一个 k 染色又称图 G 是 k-可染的。通过权转移的方法证明了不含 3 圈和 4 圈的 1-平面图是 5-可染的。

关键词: 1-平面图, 交叉点, k-可染, 交叉面

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

中图分类号:

O157.5

王晔,孙磊. 不含3圈和4圈的1-平面图是5-可染的[J]. 山东大学学报（理学版）, 2017, 52(4): 34-39.

WANG Ye, SUN Lei. Every 1-planar graph without cycles of length 3 or 4 is 5-colorable[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(4): 34-39.

参考文献

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

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed

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

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

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 2

多维度评价

本文评价

推荐阅读 0

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