\((1,0,0)\)-Colorability of planar graphs without prescribed short cycles
Let \(d_1, d_2,\ldots ,d_k\) be \(k\) non-negative integers. A graph \(G\) is \((d_1,d_2,\ldots ,d_k)\)-colorable, if the vertex set of \(G\) can be partitioned into subsets \(V_1,V_2,\ldots ,V_k\) such that the subgraph \(G[V_i]\) induced by \(V_i\) has maximum degree at most \(d_i\) for \(i=1,2,\ldots ,k\). Let \(\digamma \) be the family of planar graphs with cycles of length neither 4 nor 8. In this paper, we prove that a planar graph in \(\digamma \) is \((1,0,0)\)-colorable if it has no cycle of length \(k\) for some \(k\in \{7,9\}\). Together with other known related results, this completes a neat conclusion on the \((1,0,0)\)-colorability of planar graphs without prescribed short cycles, more precisely, for every triple \((4,i,j)\), planar graphs without cycles of length 4, \(i\) or \(j\) are \((1,0,0)\)-colorable whenever \(4<i<j\le 9\).
planar graph cycle steinberg conjecture improper coloring