图的强直积的2-距离染色

J4 ›› 2010, Vol. 45 ›› Issue (3): 66-70.

图的强直积的2-距离染色

马宝林^1,2, 陈祥恩^1*, 刘娟²

1. 西北师范大学数学与信息科学学院, 甘肃兰州 730070； 2. 河南科技学院数学系, 河南新乡 453003

收稿日期:2009-09-04 出版日期:2010-03-16 发布日期:2010-04-02

2-distance coloring of strong product of graphs

MA Bao-lin1,2， CHEN Xiang-en1*， LIU Juan2

1. College of Mathematics and Information Science, Northwest Normal University, Lanzhou 730070, Gansu, China;
2. Department of Mathematics, Henan Institute of Science and Technology, Xinxiang 453003, Henan, China

Received:2009-09-04 Online:2010-03-16 Published:2010-04-02
Contact: Chen Xiangen(1965-), male, professor, major in the research of the coloring and algebraic theory of graphs. Email: chenxe@nwnu.edu.cn
About author: MA Bao-lin(1978-), male, lecturer, graduate student, major in the research of graph theory and its application. Email: xxdsmbl@163.com
Supported by:
Supported by NNSFC (10771091)

摘要/Abstract

摘要：

G,H是阶至少为2的简单图。图G与H的强直积是指这样一个图G×H, 其顶点集合为V(G)×V(H), 并且(x₁,x₂)(y₁,y₂)∈E(G×H) 当且仅当［x₁y₁∈E(G)且x₂y₂∈E(H)］或者［x₁=y₁且x₂y₂∈E(H)］或者［x₂=y₂且x₁y₁∈E(G)］。一个图G的使用了k种颜色的2-距离染色是指一个从V(G)到｛1,2,…,k｝的映射f, 使得任意两个不同的距离最多是2的顶点染不同的颜色。对图G进行2-距离染色所需的最少的颜色数称为图G的2-距离色数, 记为χ₂(G)。文中将获得两个图的强直积的2-距离色数的可达到的上界和下界: Δ(G×H)+1≤χ₂(G×H)≤χ₂(G)·χ₂(H)。对一些特殊图, 例如Pm×Kn, Pm×Wn, Pm×Sn, Pm×Fn, Pm×Cn(n≡0(mod 3)或者n=5), 给出了它们的2-距离色数。

关键词: 图; 图的强直积; 2-距离染色; 2-距离色数

Abstract:

Let G,H be simple graphs of order at least 2. The strong product of graph G and H is the graph G×H with vertex set V(G)×V(H), and (x1,x2)(y1,y2)∈E(G×H) whenever ［x1y1∈E(G) and x2y2∈E(H)］　or ［x1=y1 and　 x2y2∈E(H)］ or ［x2=y2 and x1y1∈E(G)］. A 2distance coloring using k colors of a graph G is a mapping f from V(G) to ｛1,2,…,k｝ such that two distinct vertices lying at a distance less than or equal to 2 must be assigned different colors. The minimum number of colors required for a 2distance coloring of G is called the 2distance chromatic number of G, and denoted by χ2(G). We obtain lower and upper bounds of the 2distance chromatic number of strong product of graphs, which is Δ(G×H)+1≤χ2(G×H)≤χ2(G)·χ2(H), also shows that the bounds are tight. For some special families of graphs such as Pm×Pn, Pm×Kn, Pm×Wn, Pm×Sn, Pm×Fn, Pm×Cn(n≡0(mod 3)or =5),their 2-distance chromatic number are obtained.

Key words: graphs； strong product of graphs； 2-distance coloring； 2-distance chromatic number

马宝林1,2, 陈祥恩1*, 刘娟2. 图的强直积的2-距离染色[J]. J4, 2010, 45(3): 66-70.

MA Bao-lin1,2， CHEN Xiang-en1*， LIU Juan2. 2-distance coloring of strong product of graphs[J]. J4, 2010, 45(3): 66-70.

参考文献

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed