全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...

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

, PP. 40-44

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

Full-Text   Cite this paper   Add to My Lib

Abstract:

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

References

[1]  BONDY J A, MURTY U S R. Graph Theory with Applications[M]. New York: North-Holland, 1976.
[2]  WOODALL D R. Edge-choosability of multicircuits[J]. Discrete Mathematics, 1999, 202: 271-277.
[3]  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.
[4]  RINGEL G. Ein Sechsfarbenproblem auf der Kugel[J]. Abh Math Sem Univ, Hamburg, 1965, 29: 107-117.
[5]  ZHANG X, WU J L. On edge colorings of 1-planar graphs[J]. Information Processing Letters, 2011, 111(3): 124-128.
[6]  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.
[7]  WU J L, WANG P. List-edge and list-total colorings of graphs embedded on hyperbolic surfaces[J]. Discrete Mathematics, 2008, 308: 6210-6215.
[8]  JENSEN T R, TOFT B. Graph Coloring Problems [M]. NewYork: Wiley-Interscience, 1995.
[9]  HAGGKVIST R, CHETWYND A. Some upper bounds on the total and list chromatic numbers of multigraphs[J]. Graph Theory, 1992, 16: 503-516.
[10]  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.
[11]  PERTERSON D, WOODALL D R. Edge-choosability in line-perfect multigraphs[J]. Discrete Mathematics, 1999, 202: 191-199.
[12]  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.
[13]  GALVIN F. The list chromatic index of a bipartite multigraph[J]. Journal of Combinatorial Theory, Series B, 1995, 63: 153-158.
[14]  WAANG W, LIH K. Choosability, edge-choosability and total choosability of outerplane graphs[J].European Journal of Combinatorics, 2001, 22: 71-78.
[15]  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.

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133