Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9515954 | Journal of Combinatorial Theory, Series B | 2005 | 9 Pages |
Abstract
Planar graphs without cycles of length from 4 to 7 are proved to be 3-colorable. Moreover, it is proved that each proper 3-coloring of a face of length from 8 to 11 in a connected plane graph without cycles of length from 4 to 7 can be extended to a proper 3-coloring of the whole graph. This improves on the previous results on a long standing conjecture of Steinberg.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
O.V. Borodin, A.N. Glebov, A. Raspaud, M.R. Salavatipour,