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 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 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 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].