期刊文献+

List Total Colorings of Planar Graphs without Triangles at Small Distance 被引量:1

List Total Colorings of Planar Graphs without Triangles at Small Distance
原文传递
导出
摘要 Suppose that G is a planar graph with maximum degree △. In this paper it is proved that G is total-(△ + 2)-choosable if (1) △ ≥ 7 and G has no adjacent triangles (i.e., no two triangles are incident with a common edge); or (2) △ ≥6 and G has no intersecting triangles (i.e., no two triangles are incident with a common vertex); or (3) △ ≥ 5, G has no adjacent triangles and G has no k-cycles for some integer k ∈ {5, 6}. Suppose that G is a planar graph with maximum degree △. In this paper it is proved that G is total-(△ + 2)-choosable if (1) △ ≥ 7 and G has no adjacent triangles (i.e., no two triangles are incident with a common edge); or (2) △ ≥6 and G has no intersecting triangles (i.e., no two triangles are incident with a common vertex); or (3) △ ≥ 5, G has no adjacent triangles and G has no k-cycles for some integer k ∈ {5, 6}.
出处 《Acta Mathematica Sinica,English Series》 SCIE CSCD 2011年第12期2437-2444,共8页 数学学报(英文版)
关键词 List total coloring CHOOSABILITY planar graph List total coloring, choosability, planar graph
  • 相关文献

参考文献13

  • 1Bondy, J. A., Murty, U. S. R.: Graph Theory with Applications, MacMillan, London, 1976.
  • 2Behzad, M.: Graphs and Their Chromatic Numbers, Ph.D. Thesis, Michigan State University, 1965.
  • 3Vizing, V. G.: Some unsolved problems in graph theory (in Russian). Uspekhi Mat. Nauk, 23, 117 134 (1968).
  • 4Borodin, O. V.: On the total coloring of planar graphs. J. Reine Angew. Math., 394, 180-185 (1989).
  • 5Borodin, O. V., Kostochka, A. V., Woodall, D. R.: List edge and list total colourings of multigraphs. J. Combin. Theory Set. B, 71, 184-204 (1997).
  • 6Borodin, O. V., Kostochka, A. V., Woodall, D. R.: Total colorings of planar graphs with large maximum degree. J. Graph Theory, 26, 53-59 (1997).
  • 7Wang, W.: Total chromatic number of planar graphs with maximum degree ten. J. Graph Theory, 54, 91-102 (2007).
  • 8Wang, W., Lih, K.: Choosability, edge-choosability and total choosability of outerplane graphs. European J. Combin., 22, 71-78 (2001).
  • 9Woodall, D. R.: Total 4-choosability of series-parallel graphs. Electron. J. Combin., 13, R97, 36pp (2006).
  • 10Hou, J., Liu, G., Cai, J.: List edge and list total colorings of planar graphs without 4-cycles. Theoret. Comput. Sci., 369, 250-255 (2006).

引证文献1

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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