摘要
设G是任意的p阶连通图,V(G)={V1,V2…,Vp},Sn+1是具有度序列(n,1,1,…,1)的n+1阶星图.令(ψ)G(i)(n,p)表示图G的第i个顶点与Sn+1的n度点重迭后得到的图;SG(i)rp+1表示rG的每个分支的第i个顶点依次与Sr+1的r个1度点重迭后得到的图,这里n≥1,p≥r≥2,1≤i≤p.我们通过研究图的伴随多项式的因式分解,证明了两个图簇SG(irp+1∪(r-1)K1与(r-1)G∪ψG(i)(r,p)的补图是色等价的,但它们均不是色唯一的,从而推广了张秉儒证明的文[14]中的定理1.
Let G be an arbitrary connected graph with p vertices and V(G) = {V1, V2,…, Vp}, and let Sn+1 be a star having degree sequence (n, 1,…, 1) with n + 1 vertices. We denote by ψG(i)(n,p) the graph consisting of G and Sn+1 by coinciding the ith vertex of G with the vertex of degree n of Sn+1, and let Srp+1G(i) denote the graph obtained from rG and Sr+1 by coinciding the ith vertex of each component of rG with r vertices of degree 1 of Sr+1, respectively, (where (n ≥ l,p ≥ r ≥ 2,1 ≤ i ≤ p). By studying the factorization of adjoint polynomials of graphs, we prove two graphs Srp+1G(i)∪(r - 1)K1 and (r-1l)G∪ψG(i)(r,p) that their complements are chromatically equivalent, but everyone does not be chromatically unique. We improve Theorem 1 by Zhang Bing-ru in [14].
出处
《数学进展》
CSCD
北大核心
2004年第4期425-433,共9页
Advances in Mathematics（China）
基金
国家自然科学基金资助项目
关键词
色多项式
伴随多项式
因式分解
色等价性
非色唯一图
chromatic polynomial
adjoint polynomial
factorization
chromatically equiv- alence
chromatically non-unique graph
