数学研究
數學研究
수학연구
JOURNAL OF MATHEMATICAL STUDY
2011年
1期
1-15
,共15页
k-重染色%平面图%奇围长
k-重染色%平麵圖%奇圍長
k-중염색%평면도%기위장
k-fold coloring%Planar graph%Odd girth
G=(V,E)表示一个顶点集为V,边集为E的有限简单无向图.若存在映射φ:V(G)→Zk(n)(Zk(n)是由{1,2,…,n}的所有k-元子集构成的集合),满足:(A) uv∈E(G),有φ(u)∩φ(u)=θ,则称φ是G的一个k-重n-顶点染色.本文证明了奇围长至少为5k-7(k=4)或5k-9(k=6)的平面图G是k-重(2k+2)-可染的.
G=(V,E)錶示一箇頂點集為V,邊集為E的有限簡單無嚮圖.若存在映射φ:V(G)→Zk(n)(Zk(n)是由{1,2,…,n}的所有k-元子集構成的集閤),滿足:(A) uv∈E(G),有φ(u)∩φ(u)=θ,則稱φ是G的一箇k-重n-頂點染色.本文證明瞭奇圍長至少為5k-7(k=4)或5k-9(k=6)的平麵圖G是k-重(2k+2)-可染的.
G=(V,E)표시일개정점집위V,변집위E적유한간단무향도.약존재영사φ:V(G)→Zk(n)(Zk(n)시유{1,2,…,n}적소유k-원자집구성적집합),만족:(A) uv∈E(G),유φ(u)∩φ(u)=θ,칙칭φ시G적일개k-중n-정점염색.본문증명료기위장지소위5k-7(k=4)혹5k-9(k=6)적평면도G시k-중(2k+2)-가염적.
Let G = (V, E) be a finite, simple and undirected graph with the set of vertices V, and the set of edges E. A k-fold n-coloring of a graph G is a mapping φ : V(G) → Zk(n) (Zk(n) is the collection of all k-subsets of {1, 2,… , n} ). such that : (A)uv ∈ E(G), there is φ(u) ∩φ(v) = θ, then say G is k-fold n-colorable. We show that every planar graph with odd girth at least 5k - 7(k = 4) or 5k - 9(k = 6) can be k-fold (2k + 2)-colorable.
