图 K_n—E(kP_s∪rP_t)的色唯一性

本文仅考虑有限、无向、无环的简单图.P(G,λ)表示图 G 的色多项式.如果从P(H,λ)=P(G,λ)可以推出图 H 和 G 同构,则称 G 是色唯一的.设 G 是一个顶点数不超过 n 的图,用 K_n—E(G)表示从完全图 K_n 中删去一个和G 同构的子图的所有边而得到的图.关于 K_n—E(G)型图中的色唯一图的研究已有不少结果,参见[1—5].     

图的色数的一个上界

本文给出了图的色数的一个新上界,它改进了文献[2]中定理1.8的结论.     

图$(\bigcup\limits_{i{\in}A}P_i){\bigcup}(\bigcup\limits_{j{\in}B}U_j)$伴随唯一的充要条件

设$h(G; x) =h(G)$和$[G]_h$分别表示图$G$的伴随多项式和伴随等价类. 文中给出了$[G]_h$的一个新应用. 利用$[G]_h$, 给出了图$H{\;}(H \cong G)$伴随唯一的充要条件, 其中$H=(\bigcup_{i{\in}A}P_i){\bigcup}(\bigcup_{j{\in}B}U_j)$, $A \subseteq A^{'}=\{1,2,3,5\} \bigcup \{2n|n \in N, n \geq 3\}$, $B \subseteq B^{'}     

两类K4同胚图的色唯一性

用k4(α,b,c,d,e,f)表示k4同胚图,其中α,b,c,d,e,f分别表示度为3的顶点间的道路的长。本主要研究了两类k4同胚图的色唯一性,同时得到了几族新的不是色唯一的k4同胚图。     

几类图族伴随多项式的最小根

主要讨论了连通图G所含三角形的两个二度点分别与路、圈或Dn(由K3的一个顶点和路的一个端点重迭后所得到的图)相粘接后所得新图的伴随多项式最小根的变化情况,得到一些新结果.     

图的正常三着色的最大方法数

令F_(v,e)表示所有简单无向(v,e)-图的全体所成的集合,f(v,e,λ)=max{P(G,λ);G∈F_(v,e)}.本文改进了文献[1]中给出的f(v,e,3)的上界,并指出[1]中的猜想的充分性是不成立的.     

图K(m,n)+S的色性

设S是完全图Km 1的任一有s条边的子图,即|E(S)|=s,E(S)(∪)E(Km 1),V(S)(∪)V(Km 1).图Km 1-E(S)简单地表示为Km 1-S,而Km 1-S关于Km 1的补图记为(Km 1-S).空图Nm与(Km 1-S)的联图记为Nm∨(Km 1-S).K sm 1(m,m 1)表示图集{Nm∨(Km 1-S)| S是Km 1的子图,|S|=s}.本文证明了当m≥s 2且s≥1,〈S〉是E(s)在完全图Km 1的边导出子图并且〈S〉是二部图时,联图Nm∨(Km 1-S)为色唯一图的充要条件是〈S〉是没有割点的连通图(即〈S〉是2-连通的或〈S〉≌Ki,i=1,2)且是色唯一图.     

路的补图的色唯一性

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

直径为5的整树

“整图”这个术语首先由 F.Harary 和 A.J.Schwenk(1974)引入.所谓整图就是指其特征值均为整数的图.文献[1]给出了所有直径小于4的整树以及一类直径4的整树.文献[2]给出了无穷多个异于文献[1]所指出的直径4的整树,并找到了无穷多个直径6的整树,同时提出下面两个未解决的问题:存在直径5的整树吗?存在直径任意大的整树吗?     

一类K-4与路点粘接补图的色唯一性

利用图的伴随多项式的最小极及第四项系数，给出了一类K4^-与路点粘接补图色唯一的充要条件。