期刊文献+

On 3-colorings of Plane Graphs 被引量:2

On 3-colorings of Plane Graphs
原文传递
导出
摘要 In this paper, we prove that if G is a plane graph without 4-, 5- and 7-circuits and without intersecting triangles, then for each face f of degree at most 11, any 3-coloring of the boundary of f can be extended to G. This gives a positive support to a conjecture of Borodin and Raspaud which claims that each plane graph without 5-circuits and intersecting triangles is 3-colorable.
作者 Bao-gangXu
出处 《Acta Mathematicae Applicatae Sinica》 SCIE CSCD 2004年第4期597-604,共8页 应用数学学报(英文版)
关键词 Plane graph CIRCUIT COLORING Plane graph circuit coloring
  • 相关文献

参考文献8

  • 1Alon, N., Tarsi, M. Colorings and orientations of graphs. Combinatorics, 12(2): 125 134 (1992)
  • 2Bondy, J.A., Murty, U.S.R. Graph theory with applications. Macmillan Ltd. Press, New York, 1976
  • 3Borodin, O.V. Structural properties of plane graphs without adjacent triangles and an application to 3-colorings. Journal of Graph Theory, 21(2): 183-186 (1996)
  • 4Borodin, O.V., Raspaud, A. A sufficient condition for planar graphs to be 3-colorable. Journal of Combinatorial Theory, (Series. B), 88:17-27 (2003)
  • 5Borodin, O.V., Glebov, A.N., Raspaud, A., Salavatipour, M.R. Planar graphs without cycles of length from 4 to 7 are 3-colorable, manuscript.
  • 6Havel, I. On a conjecture of B. Griinbaum. Journal of Combinatorial Theory, 7:184 186 (1969)
  • 7Sanders, D.P., Zhao, Y. A note on the three color problem. Graphs and Combinatorics, 11:91-94 (1995)
  • 8Steinberg, R. The state of the three color problem, Quo Vadis. Graph Theory? J.Gimbel, J.W.Kennedy & L.V.Quintas (eds). Ann Discrete Math., 55:211-248 (1993)

引证文献2

二级引证文献2

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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