二部图K(m,n)-A(|A|≥2)的色唯一性

Chromatic Uniqueness of Certain Bipartite Graphs K(m,n)-A(|A|≥2)

设G是简单图 ,用P(G ,λ)表示图G的色多项式 .若对任意简单图H使P(H ,λ) =P(G ,λ) ,都有H与G同构 ,则称G是色唯一图 .用K(m ,n)表示完全二部图 ,K(m ,n) -A表示从K(m ,n)中删去边子集A所得的二部图 .令L-s2 (m ,n) ={K(m ,n) -A |A| =s}.研究一般形式的K(m ,n) -A的色唯一性问题 .通过引进色正规图类的概念 ,使用比较两个色等价图的色划分数的方法 ,得出G∈L-s2 (m ,n)的色等价图仍然是属于L-s2 (m ,n)的一般形式数值条件 ,进一步得出G∈L-s2 (m ,n) (2≤s≤ 4)为色唯一图的一般形式数值条件 .所得结果完全覆盖并推广了

Let G be a simple graph and P(G,λ) denote the chromatic polynomial of G .A graph G is said to be chromatically unique if any graph H,P(H,λ)=P(G,λ) implies that H is isomorphic to G .Let K(m,n) denote a complete bipartite graph and K(m,n)-A denote the bipartite graph obtained by deleting a set of edges A from K(m,n). Let L -s 2(m,n)={K(m,n)-A|A|=s} .The chromatic uniqueness of the general graphs K(m,n)-A was discussed.Introducing the concept of class of chromatically normal graphs and comparing the numbers of partitions into color classes of two chromatically equivatent graphs,a general numerical condition guaranteeing that the equivatent graphs of G∈L -s 2(m,n) still belong to L -s 2(m,n) was obtained.Furthermore,a general numerical condition guaranteeing that G∈L -s 2(m,n)(2≤s≤4) is chromatically unique was obtained.The results completely covered and extended the related results of this research direction before 1997.