A Relaxation of Steinberg's Conjecture

Abstract

A graph is $(c_1, c_2, \ldots, c_k)$-colorable if the vertex set can be partitioned into $k$ sets $V_1,V_2, \ldots, V_k$, such that for every $i: 1\leq i\leq k$ the subgraph $G[V_i]$ has maximum degree at most $c_i$. We show that every planar graph without $4$- and $5$-cycles is $(1, 1, 0)$-colorable. This is a relaxation of the Steinberg conjecture that every planar graph without $4$- and $5$-cycles are properly $3$-colorable (i.e., $(0,0,0)$-colorable).