k-fold coloring of planar graphs |
| |
Authors: | GuanFeng Ren YueHua Bu |
| |
Affiliation: | 1. Department of Mathematics, Zhejiang Normal University, Jinhua, 321004, China
|
| |
Abstract: | A k-fold n-coloring of G is a mapping φ: V(G) → Z k (n) where Z k (n) is the collection of all k-subsets of {1, 2,..., n} such that φ(u) ∩ φ(v) = $ \not 0 $ if uv ∈ E(G). If G has a k-fold n-coloring, i.e., G is k-fold n-colorable. Let the smallest integer n such that G is k-fold n-colorable be the k-th chromatic number, denoted by χk (G). In this paper, we show that any outerplanar graph is k-fold 2k-colorable or k-fold χk (C*)-colorable, where C* is a shortest odd cycle of G. Moreover, we investigate that every planar graph with odd girth at least 10k ? 9 (k ? 3) can be k-fold (2k + 1)-colorable. |
| |
Keywords: | |
本文献已被 CNKI SpringerLink 等数据库收录! |
|