List edge and list total coloring of triangle-free 1-planar graphs
-
摘要: 一个图称为是~1-平面的,当且仅当它可以画在一个平面上,使其任何一 条边最多交叉另外一条边. 本文证明了最大度 ~$\Delta\geqslant15$ 且不含三角形的~1-平面图~$G$ 是 ~$\Delta$-边可选择的和~($\Delta$+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
-
{[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.
点击查看大图
计量
- 文章访问数: 1311
- HTML全文浏览量: 12
- PDF下载量: 1896
- 被引次数: 0