可平面图的r-hued染色(英文)  

On r-hued Coloring of Planar Graphs

作　　者：朱海洋[1] 顾毓[1] 盛景军[1] 吕新忠[2] 

机构地区：[1]空军勤务学院飞行保障指挥系,江苏徐州221000 [2]浙江师范大学数学系,浙江金华321004

出　　处：《应用数学》2016年第2期308-313,共6页Mathematica Applicata

基　　金：Supported by the National Natural Science Foundation of China(61170302)

摘　　要：令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.

关 键 词：r-hued染色 可平面图 圈 Wagner猜想 

分 类 号：O157.5[理学—数学]