路的补图的色唯一性(英文)

设 Pn 表示n阶的路 .文 [2 ]中刘猜测 :如果 n是偶数且 n≠ 4 ,则 Pn 色唯一的 .本文得到 Pn 色唯一的充要条件 ,从而肯定的回答了刘提出的猜测 .

一类K_n－E（G）型图的色唯一性

设Ｋｍ－Ｅ（Ｇ）表示从完全图Ｋｍ中删去一个和Ｇ同构的子图的所有边而得到的图．本文证明了，当Ｇ＝ｋ１Ｐｓ１∪ｋ２ＰＳ２∪…∪ｋｒＰｓｒ，（ｓｉ＞１，ｓｉ≠４，ｉ＝１，２，…，ｒ），且Ｐｓｉ都是不可约路时，图Ｋｍ－Ｅ（Ｇ）是色唯一的．

一类 K_4^-与路点粘接补图的色唯一性

利用图的伴随多项式的最小根及第四项系数 ,给出了一类 K-4 与路点粘接补图色唯一的充要条件 .

不可约圈并的补图的色唯一性

本文证明了:如果对于每个i∈{1,2,…,k},都有n_i≥5,且n_i是2的幂或素数,则是色唯一图。

关于圈并的补图的色唯一性

本文证明了猜测:()_p,p≥5是色唯一的(Farrell 和 Whitehead),还讨论了圈并的补图的色唯一性.

完全三部图K(n-k,n-v,n)的色唯一性

设P(G,λ)是图G的色多项式,如果任意与图G的色多项式相等(P(G,λ)=P(H,λ))的图H都与图G同构(GH),则称图G是色唯一图.文献[Lau G C,Peng Y H.Chromatic uniqueness ofcertain complete tripartite graphs.Acta Mathematica Sinica,English Series,2011,27(5):919-926]中提出一个猜想(若k≥v≥2,n≥k2/4+v+1,则完全三部图K(n-k,n-v,n)是色唯一的),并证明了若2≤v≤4,k≥v≥2,n≥k2/4+v+1,则K(n-k,n-v,n)是色唯一的.通过比较三角形子图和无弦四边形子图的个数,证明了若v≥4,k≥2v2+4,n≥(k+2)2/8+3,则K(n-k,n-v,n)是色唯一图。

连通的顶点可迁图的色唯一性

本文给出从一个已知的顶点可迁的非色唯一图出发,构造无穷多个顶点可迁的非色唯一图的一种方法,据此给出若干类无穷多个连通的顶点可迁,但不是色唯一的图簇,从而进一步否定地回答了Chia在[1]中提出的问题.

一类图的色唯一性

设Ｐ＿ｍ表示有ｍ个顶点的路。把Ｋ＿３的一个顶点与Ｐ＿（ｎ－２）的一个一度顶点重迭后所得到的图记为Ｄ＿ｎ。本文引入了不可约图的概念，并证明了：如果对任意的ｉ∈｛１，２，…ｒ｝，都有ｎ＿ｉ≥５，并且Ｄ＿ｎ＿ｉ是不可约图，则Ｄ＿ｎ＿１∪Ｄ＿ｎ＿２∪…∪Ｄ＿ｎ＿ｒ的补图是色唯一图。

完全3部图K(n-k,n-3,n)色唯一性的证明（英文）

设P(G,λ)是图G的色多项式,如果任意与图G的色多项式相等(P(G,λ)=P(H,λ))的图H都与图G同构(G≌H),则称图G是色唯一图.这里,通过比较图的三角形子图和无弦四边形的个数,完全解决了一类完全三部图K(n-k,n-3,n)的色唯一性问题,证明了,若n≥k+2≥5,则完全三部图K(n-k,n-3,n)是色唯一图.

完全三部图色唯一性数值条件的改进

设P(G,λ)是图G的色多项式,如果任意与图G的色多项式相等(P(G,λ)=P(H,λ))的图H都与图G同构(G■H),则称图G是色唯一图.这里通过比较图的三角形子图和无弦四边形子图的个数,讨论了完全三部图K(n-k,n-v,n)的色唯一性.证明了若n≥v^2(k-v/3)/4+v,k≥v≥2,则完全三部图K(n-k,n-v,n)是色唯一图;若n≥k+2,k≥2,则完全三部图K(n-k,n-2,n)是色唯一图.

两类图并补图的色唯一性

刘儒英介绍了图的特征标R(G),并分别给出当R(G)=0和R(G)=1时图类所具有的性质并对图类进行描述,本文推广此结果,讨论了R(G)=-1和R(G)=-2时的情形,并证明了两类具备一定性质的图并的补图的色唯一性.

关于色唯一性的一个注记

本文给出了构造伴随等价图的几种办法。证明了当ｎ趋于无穷大时，在ｎ个顶点的所有树中，伴随唯一的树的比率趋于零。

D_n补图的色唯一性

利用伴随多项式来讨论图的着色唯一性是近二十年来出现的新方法.用Pn表示有n个顶点的路.Dn表示把K3的一个顶点与Pn-2的一个一度顶点重迭后得到的图.该文推广了相关文献的结论,得到Dn色唯一当且仅当n≠4且n≠8.彻底解决了这类图的色性.

二部图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)为色唯一图的一般形式数值条件 .所得结果完全覆盖并推广了

图K_n-E(kP_s∪_rK_3)的色唯一性

利用不可约路的概念，证明了当Ｐｓ是不可约的路时，Ｋｎ－Ｅ（ｋＰｓ∪ｒＫ３）是色唯一的图，其中设Ｋｎ－Ｅ（Ｇ）表示从完全图Ｋｎ中删去一个和Ｇ同构的子图的所有边而得到的图，ｓ≠４，且ｋｓ＋３ｒ＝ｎ，ｋ３是有３个顶点的完全图．

一类图的色唯一性

利用图的色多项式和图的结构间的内在联系，以及图的色数和点的度之间的关系，把满足一定条件的图分成几种情形．证明了当ｎ ≥３ ，ｍ ≥３ 时，由完全图Ｋｎ 和圈Ｃｍ 重叠于一条边得到的一类新图是色唯一的．

“图的色等价性与色唯一性”研究取得突破性进展

“图论”是具有广泛实用背景的新兴数学分支,它在计算机科学、运筹学、网络理论等许多领域都有广泛的应用。因此,本世纪50年代以来,图论得到了蓬勃的发展。“图的色多项式”是用代数方法来描述图的特征的工具之一,因而成为图论的重要研究对象。 1978年,美国学者Chao C.Y.和Whitehead E.G.提出的“图的色等价性与色唯一性”概念把图的色多项式研究推向了新的高潮。色等价的图是指具有相同色多项式的图。

图K_n-E(k_0P_3(∪ri=1k_iP(q_i-1)))的色唯一性

记δｎ＝ｋ≤ｎｋｎ－ｋ，在本文中证明了：ｒ∈Ｎ，若ｉ∈｛１，２，…，ｒ｝，ｑｉ（＞５）都是素数，并且［（δｑｉ－１－１）！＋１］／δｑｉ－１是正整数，则图簇Ｋｎ－Ｅｋ０Ｐ３∪ｋ１Ｐｑ１－１∪ｋ２Ｐｑ２－１∪…∪ｋｒＰｑｒ－１是色唯一的。

关于完全三部图K(n,n,n+4)的色唯一性

通过比较两个图的色多项式的系数(本文使用了五独立集数)、顶点集、边集、三角形和四圈的个数,证明了K(2,2,6)是色唯一图,从而部分地回答了文[5],[7]中遗留的一个问题,并得到图K(n,n,n+4)(n=2或n 4)是色唯一的.

不可约圈与路之并补图的色唯一性

讨论了形如ｋＣＲＵｒＰＲ的一类图的补图的色性．在一定的条件下证明了这类图是色唯一的．本文推广了文［１］的结果．