最大度至多为5的平面图的单射染色

作者：朱海洋; 盛景军; 张玉杰; 葛生联

来源：山东理工大学学报(自然科学版), 2011, (02): 25-29.

DOI：10.13367/j.cnki.sdgc.2011.02.005

• 平面图
• 单射染色
• 单射色数
• 围长 planar graph
• injective coloring
• injective chromatic number
• girth

图G的一个单射k-染色是一个映射f:V(G)→{1,…,k},其中f满足对任意的不同顶点u,v∈V(G),若u和v具有共同的相邻顶点,则f(u)≠f(v).并称iχ(G)=min{k|G存在一个单射k-染色}为图G的单射色数.证明了若G是最大度Δ(G)≤5且围长g(G)≥5的平面图,则iχ(G)≤Δ(G)+6.此界限好于之前关于Δ(G)≤5和g(G)≥5的平面图G的证明结果.

• 单位
  中国人民解放军空军指挥学院