期刊文献+

List edge and list total coloring of 1-planar graphs 被引量:6

List edge and list total coloring of 1-planar graphs
原文传递
导出
摘要 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 is proved that each 1-planar graph with maximum degree △ is (A + 1)-edge-choosable and (△ + 2)- total-choosable if △ ≥ 16, and is A-edge-choosable and (△ + 1)-total-ehoosable if △ ≥21. The second conclusion confirms the list coloring conjecture for the class of 1-planar graphs with large maximum degree. 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 is proved that each 1-planar graph with maximum degree △ is (A + 1)-edge-choosable and (△ + 2)- total-choosable if △ ≥ 16, and is A-edge-choosable and (△ + 1)-total-ehoosable if △ ≥21. The second conclusion confirms the list coloring conjecture for the class of 1-planar graphs with large maximum degree.
机构地区 School of Mathematics
出处 《Frontiers of Mathematics in China》 SCIE CSCD 2012年第5期1005-1018,共14页 中国高等学校学术文摘·数学(英文)
关键词 1-planar graph list coloring conjecture DISCHARGING 1-planar graph, list coloring conjecture, discharging
  • 相关文献

参考文献1

二级参考文献18

  • 1Bondy J A, Murty U S R. Graph Theory with Applications [M]. New York: North-Holland, 1976.
  • 2Akiyama J, Exoo G, Haraxy F. Covering and packing in graphs Ⅲ: Cyclic and acyclic invariants [J]. Math Slovaca, 1980, 30: 405-417.
  • 3Wu J L. On the linear arboricity of planar graphs [J]. J. Graph Theory, 1999, 31: 129-134.
  • 4Wu J L, Wu Y. The linear arboricity of planar graphs of maximum degree seven is four [J]. J. Graph Theory, 2008, 58: 210-220.
  • 5Peroche B. Complexity of the linear arboricity of a graph [J]. RAIRO Rech. Oper., 1982, 16: 125-129.
  • 6Wu J L. The linear arboricity of graphs on surfaces of negative Euler characteristic [J]. SIAM J Discrete Math, 2008, 23(1): 54-58.
  • 7Wu J L. The linear arboricity of series-parallel graphs [J]. Graphs Combin, 2000, 16: 367-372.
  • 8Ringel G. Ein sechsfarbenproblem auf der kugel [J]. Abh. Math. Semin. Univ. Hamburg, 1965, 29: 107-117.
  • 9Borodin O V. Solution of Ringel's problems on the vertex-face coloring of plane graphs and on the coloring of 1-planar graphs [J]. Metody Diskret Analiz, 1984, 41: 12-26.
  • 10Borodin O V. A New Proof of the 6-Color Theorem [J]. J Graph Theory, 1995, 19(4): 507-521.

共引文献7

同被引文献21

引证文献6

二级引证文献8

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部