k-FOLD (2k + 1)-COLORING OF PLANAR GRAPHS
Yuehua Bu, YUDIE WU · Discrete Mathematics Algorithms and Applications · 2011
A k-fold n-coloring of a graph G is an assignment of k distinct colors to each vertex of G from n colors, such that adjacent vertices receive no colors in common. If G has a k-fold n-coloring, then say G is k-fold n-colorable. Denote the kth chromatic number of G by χk(G), i.e. χk(G) = min {n : G is k- fold n- colorable }. We show that every planar graph with odd girth at least 6k + 1(k = 3) or 6k - 1(k = 2) can be k-fold (2k + 1)-colorable.