不含3-圈的1-平面图的列表边染色与列表全染色

华东师范大学学报(自然科学版) ›› 2014, Vol. 2014 ›› Issue (3): 40-44.

不含3-圈的1-平面图的列表边染色与列表全染色

宋文耀, 苗连英, 张淑洁

中国矿业大学~~理学院, 江苏~~徐州 221016

收稿日期:2013-05-01 修回日期:2013-08-01 出版日期:2014-05-25 发布日期:2014-07-25

List edge and list total coloring of triangle-free 1-planar graphs

SONG Wen-yao, MIAO Lian-ying, ZHANG Shu-jie

College of Sciences, China University of Mining and Technology, Xuzhou Jiangsu 221016, China

Received:2013-05-01 Revised:2013-08-01 Online:2014-05-25 Published:2014-07-25

摘要/Abstract

摘要： 一个图称为是~1-平面的，当且仅当它可以画在一个平面上，使其任何一
条边最多交叉另外一条边. 本文证明了最大度 ~$\Delta\geqslant15$
且不含三角形的~1-平面图~$G$ 是
~$\Delta$-边可选择的和~($\Delta$+1)-全可选择的.

关键词: 1-平面图, 差值转移方法, 最大度, 可选择性

Abstract: 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. In this paper, it
was proved that every triangle-free 1-planar graph $G$ with maximum
degree $\Delta\geqslant15$ can be $\Delta$-edge-choosable and
($\Delta$+1)-total -choosable.

Key words: 1-planar, discharging method, maximum degree, choosability

中图分类号:

O211

宋文耀, 苗连英, 张淑洁. 不含3-圈的1-平面图的列表边染色与列表全染色[J]. 华东师范大学学报(自然科学版), 2014, 2014(3): 40-44.

SONG Wen-yao, MIAO Lian-ying, ZHANG Shu-jie. List edge and list total coloring of triangle-free 1-planar graphs[J]. Journal of East China Normal University(Natural Sc, 2014, 2014(3): 40-44.

参考文献

{[1]} BONDY J A, MURTY U S R. Graph Theory with Applications[M]. New York: North-Holland, 1976.
{[2]} JENSEN T R, TOFT B. Graph Coloring Problems [M]. NewYork: Wiley-Interscience, 1995.
{[3]} HAGGKVIST R, CHETWYND A. Some upper bounds on the total and list chromatic numbers of multigraphs[J]. Graph Theory, 1992, 16: 503-516.
{[4]} BORODIN O V, KOSTOCHKA A V, WOODALL D R. List edge and list total colorings of multigraphs[J]. Journal of Combinatorial Theory Series B, 1997, 71: 184-204.
{[5]} PERTERSON D, WOODALL D R. Edge-choosability in line-perfect multigraphs[J]. Discrete Mathematics, 1999, 202: 191-199.
{[6]} HAGGKVIST R, JANSSEN J. Now bounds on the list-chromatic index of the complete graph and other simple graphs[J]. Combinatorics, Probability and Computing, 1997, 6: 295-313.
{[7]}GALVIN F. The list chromatic index of a bipartite multigraph[J]. Journal of Combinatorial Theory, Series B, 1995, 63: 153-158.
{[8]} WOODALL D R. Edge-choosability of multicircuits[J]. Discrete Mathematics, 1999, 202: 271-277.
{[9]} WAANG W, LIH K. Choosability, edge-choosability and total choosability of outerplane graphs[J].European Journal of Combinatorics, 2001, 22: 71-78.
{[10]} HOU J, LIU G, CAI J. List edge and list total colorings of planar graphs without 4-cycles[J]. Theoretical Computer Science, 2006, 369: 250-255.
{[11]} ZHANG X, WU J L, LIU G. List edge and list total coloring of 1-planar graphs[J]. Frontiers of Mathematics in China, 2012, 7(5): 1005-1018.
{[12]} RINGEL G. Ein Sechsfarbenproblem auf der Kugel[J]. Abh Math Sem Univ, Hamburg, 1965, 29: 107-117.
{[13]} ZHANG X, WU J L. On edge colorings of 1-planar graphs[J]. Information Processing Letters, 2011, 111(3): 124-128.
{[14]} ZHANG X, LIU G, WU J L. Edge coloring of trangle-free 1-planar graphs[J]. Joumal of Shandong University: Natural Science, 2010, 45: 15-17.
{[15]} WU J L, WANG P. List-edge and list-total colorings of graphs embedded on hyperbolic surfaces[J]. Discrete Mathematics, 2008, 308: 6210-6215.