Title: Plane graphs without 4- and 5-cycles and without ext-triangular 7-cycles are 3-colorable,
Abstract: Listed as No. 53 among the one hundred famous unsolved problems in [J. A.
Bondy, U. S. R. Murty, Graph Theory, Springer, Berlin, 2008] is Steinberg's
conjecture, which states that every planar graph without 4- and 5-cycles is
3-colorable. In this paper, we show that plane graphs without 4- and 5-cycles
are 3-colorable if they have no ext-triangular 7-cycles. This implies that (1)
planar graphs without 4-, 5-, 7-cycles are 3-colorable, and (2) planar graphs
without 4-, 5-, 8-cycles are 3-colorable, which cover a number of known results
in the literature motivated by Steinberg's conjecture.