A relaxation of Steinberg's Conjecture

Abstract

A graph is $(c_1,c_2,...,c_k)$-colorable if the vertex set can be partitioned into $k$ sets $V_1,V_2,...,V_k$, such that for every $i:1\le i\le 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 and $(3,0,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).

18 pages, 12 figures