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

Injective coloring of planar graphs with maximum degree Δ(G)≤5

作　　者：朱海洋[1] 盛景军[1] 张玉杰[1] 葛生联[1] 

机构地区：[1]徐州空军学院后勤指挥系,江苏徐州221000

出　　处：《山东理工大学学报（自然科学版）》2011年第2期25-29,共5页Journal of Shandong University of Technology:Natural Science Edition

摘　　要：图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的证明结果.An injective k-coloring of a graph G is a mapping f：V（G）→{1,…,k} such that f（u）≠f（v） for each u,v∈V（G）,whenever u and v are two distinct vertices which are adjacent to the same vertex.The injective chromatic number χi（G） of G is the least k such that G has an injective k-coloring.In this paper,we show that if G is a planar graphs with Δ（G）≤5 and girth g（G）≥5,then χi（G）≤Δ（G）＋6.This bound is better than previous result for the planar graph G with Δ（G）≤5 and g（G）≥5.

关 键 词：平面图 单射染色 单射色数 围长 

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