平面图3色可染的一个充分条件

Steinberg猜想既没有4-圈又没有5-圈的平面图是3色可染的. Xu, Borodin等人各自独立地证明了既没有相邻三角形又没有5-和7-圈的平面图是3 色可染的. 作为这一结果的推论, 没有4-, 5-和7-圈的平面图是3色可染的. 本文证明一个比此推论更接近Steinberg猜想的结果, 设G是一个既没有4-圈又没有5-圈的平面图, 若对每一个k∈{3, 6, 7}, G都不含(k, 7)-弦, 则G是3色可染的, 这里的(k, 7)-弦是指长度为7+k-2的圈的一条弦, 它的两个端点将圈分成两条路, 一条路的长度为6, 另一条路的长度为k-1.

A sufficient condition for a planar graph to be 3-colorable

Steinberg conjectured that every planar graph with neither cycle of length 4 nor cycle of length 5 is 3-colorable. Xu, independently, Borodin et al. proved that planar graphs without adjacent triangles and without 5- and 7-cycles are 3-colorable. As a corollary of this result, planar graphs without 4-, 5- and 7-cycles are 3-colorable. In this paper, we prove a result which is closer to the Steinberg''s conjecture than the corollary mentioned above. Let G be a planar graph without 4- and 5-cycles. G is 3-colorable if it has no (k, 7)-chords for each k ∈ {3, 6, 7}, where a (k, 7)-chord is a chord of a cycle of length 7 + k-2 whose two ends divide the cycle into two paths, one of which is of length 6 and the other of length k-1.