二部图K(m,m+4)-A(|A|=2)的色唯一性

The Chromatic Uniqueness of Bipartite Graphs K(m,m+4)-A (|A|=2)

设 P( G,λ)表示简单图 G的色多项式 .若对任意简单图 H使 P( H ,λ) =P( G,λ) ,都有 H与 G同构 ,则称 G是色唯一图 .令 K( m,n) -A表示从完全二部图 K( m,n)中删去边子集 A所得的二部图 .证明 :当 m≥ 3 ,K ( m,m +4) -A,|A|=2 ,是色唯一图 .

Let G be a simple graph and P(G,λ) denote the chromatic polynomial of G. Then G is said to be chromatically unique if for any simple grpah H, P(H,λ)=P(G,λ) implies that H is isomorphic to G. Let K(m,n)-A denote the bipartite graph obtained by deleting two edges from a complete bipartite graph K(m,n). In this paper we prove that K(m,m+4)-A, |A|=2, is chromatically unique if m≥3.