完全图和星的合成的点可区别正常边染色(英文)

Vertex-distinguishing proper edge coloring of composition of complete graph and star

首先,给出了完全图K_p和星S_q的合成的点可区别正常边色数的一个上界:当p≥2,q≥4时,上界是pq+1.再利用正多边形的对称性以及组合分析的方法来构造染色,分别得到了当p=2,q≥4;p≥3,q=4;p是偶数且p≥4,q=5;pq是奇数且p≥3,q≥5时,完全图K_p和星S_q的合成的点可区别正常边色数.

Firstly,we gave an upper bound for the vertex-distinguishing proper edge chromatic number of composition of complete graph K_p and star S_q,which is pq ＋ 1 for p≥2,q≥4.Then by constructing coloring in terms of the symmetry of regular polygons and the methods of combinatorial analysis,we obtained respectively vertex-distinguishing proper edge chromatic numbers for composition of complete graph K_p and star S_q when p = 2,q≥4;p≥3,q = 4;p is even and p≥4,q = 5;pq is odd and p≥3,q≥5.