Cartesian积图的关联色数与邻点可区别关联色数

The incidence chromatic number and the adjacent vertex distinguishing incidence chromatic number of Cartesian product

图G的一个关联着色是指从关联集I(G)到颜色集C的一个映射,使得任意两个相邻的关联不着同色;而图G的邻点可区别关联着色是要求任何相邻顶点具有不同色集的关联着色。研究星分别与星、扇和轮的Cartesian积图的关联着色和邻点可区别关联着色,利用构造染色的方法,确定其关联色数与邻点可区别关联色数都是最大度加一。

An incidence coloring of a graph G is a mapping from the incidence set I（G） to color set C such that any two neighborly incidences are assigned different colors. An adjacent vertex distinguishing incidence coloring of a graph G is an incidence coloring of the G such that no pair of adjacent vertices have the same set of colors. The incidence coloring and the adjacent vertex distinguishing incidence colo- ring of Cartesian product of star and star, fan and wheel are studied, respectively. By using the method of constructing dyeing, it is shown that their incidence chromatic numbers and the adjacent vertex distin- guishing incidence chromatic numbers are maximum degree plus one.