几类图的调和着色数的估计

ESTIMATE OF THE HARMONIOUS CHROMATIC NUMBER OF SOME FAMILY OF GRAPHS

引言设 V(G),E(G)分别表示无向单纯图 G 的顶点集和边集.称 V(G)到集{1,2,…,k}上的映射 f 为 G 的一个 k-着色.如果 u、v 是边 e 的两个端点,称 f(e)={f(u),f(v)}是 e 的色对.如果在 G 的一个着色中,相邻的点有不同的色,不同的边有不同的色对,则称此着色是调和的.使 G 能有 k-调和着色的最小整数 k 被称为 G 的调和着色数,记作 h(G).

The harmonious chromatic number of a graph G,denoted by h(G),is the least number ofcolors which can be assigned to the vertices of G such that adjacent vertices are colored differ-ently and any two distinct edges have different color pairs.Finding the harmonious chromaticnumber of a graph is quite difficult.But some estimates for harmonious chromatic numberhave been studied in papers [1-7].In [5] we have obtained an upper bound for h(G) i.e.h(G)(?)2Δ(?),where Δ is the maximum degree of G,and p is the order of G.In this pa-per we show that the coefficient 2Δ can be decreased for some family of graphs.