摘要
简单图G(V,E)的2-距离着色是正常的顶点着色且距离不大于2的任意两个顶点着不同的颜色.给出了网格的2-距离色数,并通过运用线图构造了一类特殊图,从而证明了最大度为Δ的图G的二距离色数的界为5/16Δ2+3/8Δ+156≤χ2dG≤min{Δ2+1,n}
The 2-distance coloring of a simple graph G is a proper coloring such that no two vertices at distance less than or equal to 2 in G are assigned the same color.A bound of on 2-distance chromatic number of grid is obtained,and show that the bounds of any graph G with maximum degree Δ are 5/16Δ2＋3/8Δ＋5/16≤χ2d（G）≤min{Δ2＋1,n} by constructing a family of special graphs by using line graph.
出处
《西南师范大学学报（自然科学版）》
CAS
CSCD
北大核心
2009年第3期17-20,共4页
Journal of Southwest China Normal University(Natural Science Edition)
基金
重庆市科委自然科学基金计划资助项目(CSTC
2007BB2123)
关键词
2-距离着色
2-距离色数
线图
网格
2-distance coloring
2-distance chromatic number
line graph
grid
