On $(3,1)^*$-Coloring of Plane Graphs

Given positive integers k and d, a graph G is said to be $(k,d)^*$-colorable if the vertices of G can be colored with k colors such that every vertex has at most d neighbors receiving the same color as itself. Let ${\cal G}$ be the family of plane graphs with neither adjacent triangles nor cycles of length 5. It is proved in this paper that every graph in ${\cal G}$ is $(3,1)^*$-colorable. This result is sharp in the sense that there exist non-$(2,1)^*$-colorable plane graphs with neither triangles nor cycles of length 5. As a corollary, after removing a matching, every graph in ${\cal G}$ is 3-colorable. This provides a partial solution to a conjecture of Borodin and Raspaud [J. Combin. Theory Ser. B, 93 (2003), pp. 17–27].