Article ID Journal Published Year Pages File Type
9513258 Discrete Mathematics 2005 4 Pages PDF
Abstract
Steinberg asked whether every planar graph without 4 and 5 cycles is 3-colorable. Borodin, and independently Sanders and Zhao, showed that every planar graph without any cycle of length between 4 and 9 is 3-colorable. We improve this result by showing that every planar graph without any cycle of length 4, 5, 6, or 9 is 3-choosable.
Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Preview
A note on 3-choosability of planar graphs without certain cycles
Authors
, ,