摘要
令k>0,r>0是两个整数.图G的一个r-hued染色是一个正常k-染色?使得每个度为d(v)的顶点v相邻至少min{d(v),r}个不同的颜色.图G的r-hued色数是使得G存在r-hued染色的最小整数k,记为χ_r(G).文章证明了,若G为不含i-圈,4≤i≤9,的可平面图,则χ_r(G)≤r+5.这一结果意味着对于无4-9圈的可平面图,r-hued染色猜想成立.
Let k, r be integers with k〉 0 and r 〉0. An r-hued coloring of a graph G is a proper k-coloring ？ such that for any vertex v with degree d（v）, v is adjacent to at least min{d（v）, r} different colors. The r-hued chromatic number of G, χ_r（G）, is the least integer k such that an r-hued coloring of G exists. In this paper, we show that if G is a planar graph without i-cycles, 4 ≤ i ≤ 9, then χ_r（G） ≤ r ＋ 5. This result implies that for a planar graph without 4-9 cycles, a conjecture on r-hued coloring of planar graphs holds.
出处
《应用数学》
CSCD
北大核心
2016年第2期308-313,共6页
Mathematica Applicata
基金
Supported by the National Natural Science Foundation of China(61170302)
