Planar graphs without adjacent cycles of length at most five are (2, 0, 0)-colorable
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 \in \{ 1, \ldots , k\}\). \textit{C. Zhang} et al. [Discrete Math. 339, No. 12, 3032--3042 (2016; Zbl 1343.05054)] asked whether every planar graph without adjacent cycles of length at most 5 is (1, 0, 0)-colorable. \textit{M. Chen} et al. [ibid. 339, No. 2, 886--905 (2016; Zbl 1327.05073)] approximated this conjecture by proving that every planar graph without cycles of length 4 and 5 is (2, 0, 0)-colorable. The authors improve this result by proving that every planar graph without adjacent cycles of length at most five is (2, 0, 0)-colorable.
scientific article; zbMATH DE number 7339965
scientific article