6n+5阶的6部图的色性

得到了几类色唯一的6n 5阶的6部图.     

Chromatic uniqueness of certain complete tripartite graphs

Let P(G, λ) be the chromatic polynomial of a graph G. A graph G is chromatically unique if for any graph H, P(H, λ) = P(G, λ) implies H is isomorphic to G. Liu et al. [Liu, R. Y., Zhao, H. X., Ye, C. F.: A complete solution to a conjecture on chromatic uniqueness of complete tripartite graphs. Discrete Math., 289, 175–179 (2004)], and Lau and Peng [Lau, G. C., Peng, Y. H.: Chromatic uniqueness of certain complete t-partite graphs. Ars Comb., 92, 353–376 (2009)] show that K(p − k, p − i, p) for i = 0, 1 are chromatically unique if p ≥ k + 2 ≥ 4. In this paper, we show that if 2 ≤ i ≤ 4, the complete tripartite graph K(p − k, p − i, p) is chromatically unique for integers k ≥ i and p ≥ k ²/4 + i + 1.     

图的伴随多项式的两个因式分解定理及其应用

设G是m阶连通图,P_m是m个顶点的路.令S_km+1^G(i)表示把kG的每一个分支的第i(1≤i≤m)个顶点依次与星图S_k+1的k个1度顶点重迭后得到的图;令G_i1^S*(q,km)表示q阶图G的顶点V_i1与S_km+1^p(1)的k度顶点重迭后得到的图     

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

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

On the chromaticity of complete multipartite graphs with certain edges added

Let P(G,λ) be the chromatic polynomial of a graph G. A graph G is chromatically unique if for any graph H, P(H,λ)=P(G,λ) implies H is isomorphic to G. For integers k≥0, t≥2, denote by K((t−1)×p,p+k) the complete t-partite graph that has t−1 partite sets of size p and one partite set of size p+k. Let K(s,t,p,k) be the set of graphs obtained from K((t−1)×p,p+k) by adding a set S of s edges to the partite set of size p+k such that 〈S〉 is bipartite. If s=1, denote the only graph in K(s,t,p,k) by K⁺((t−1)×p,p+k). In this paper, we shall prove that for k=0,1 and p+k≥s+2, each graph G∈K(s,t,p,k) is chromatically unique if and only if 〈S〉 is a chromatically unique graph that has no cut-vertex. As a direct consequence, the graph K⁺((t−1)×p,p+k) is chromatically unique for k=0,1 and p+k≥3.     

Chromaticity of certain tripartite graphs identified with a path

For a graph G, let P(G) be its chromatic polynomial. Two graphs G and H are chromatically equivalent if P(G)=P(H). A graph G is chromatically unique if P(H)=P(G) implies that H≅G. In this paper, we classify the chromatic classes of graphs obtained from K_2,2,2∪P_m(m?3), (K_2,2,2-e)∪P_m(m?5) and (K_2,2,2-2e)∪P_m(m?6) by identifying the end-vertices of the path P_m with any two vertices of K_2,2,2, K_2,2,2-e and K_2,2,2-2e, respectively, where e and 2e are, respectively, an edge and any two edges of K_2,2,2. As a by-product of this, we obtain some families of chromatically unique and chromatically equivalent classes of graphs.     

完全六部图是S-整图的一个充要条件

在他人研究完全多部图的邻接谱的基础上,对整完全多部图的Seidel多项式进行研究分析,以期得到完全六部图G是S-整图的充要条件．从讨论完全六部图的Seidel多项式入手,应用矩阵行初等变换的方法给出完全六部图G是S-整图的充要条件．     

完全五部图的S-整图性研究

应用矩阵的初等变换得到了完全五部图的 Seidel 多项式,并给出了完全五部图是S-整图的一个充分必要条件。进一步刻画了完全正则五部图和两类特殊完全五部图的Seidel谱。     

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

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

S~s一类图簇的伴随多项式的因式分解及色性分析

通过研究图的伴随多项式的因式分解 ,给出了证明非色唯一图的一种新方法 ,并且得到了色等价图的一些结构特性 .     

ED(i)形图簇的伴随多项式的因式分解及色性分析

令Dm表示三阶完全圈K3的一个顶点与路Pm-2的一个1度点重迭后得到的图；ψD^(i)(k,m），表示把Dm的第i个顶点（第1个顶点是1度点）与星图Sk 1的k度点重迭后得到的图；Erm r-1^D(i)表示把rDm中一个分支的第i个顶点与Sr的r-1度点重迭，同时把其余r-1个分支的第i个顶点分别与Sr的r-1个1度点都依次连一条边后得到的图。我们证明了对于1≤i≤m,r≥2，科簇Erm r-1^D(i) ∪(r-1)K1与Dm∪(r-2)ψD^(i)(1,m)∪ψD^(i)(r,m)两的补图是色等价的。     

The Chromaticity of Certain Complete Multipartite Graphs

In this paper, we first establish a useful inequality on the minimum real roots of the adjoint polynomials of the complete graphs. By using it, we investigate the chromatic uniqueness of certain complete multipartite graphs. An unsolved problem (i.e., Problem 11), posed by Koh and Teo in Graph and Combin. 6(1990) 259–285, is completely solved by giving it a positive answer. Moreover, many existing results on the chromatic uniqueness of complete multipartite graphs are generalized.Acknowledgments. The authors are greatly indebted to the referees for their valuable comments and suggestions, which are very helpful for improving the presentation of the paper. The work is supported by National Science Foundation of China and the Science Foundation of the State Education Ministry of China.Final version received: January 9, 2004AMS Subject Classification (2000): 05C15, 05C60     

具有色多项式∏∑(ui)/(k)(k)/(ui-k)(λ)k的图

本文利用色多项式的性质,讨论了具有色多项式∏i∑kui/k（k/ui-k）（λ）k的图的结构,给出了具有这种色多项式的全部色等价图.     

关于K4-同胚图色性的研究

We introduce a new method for studying the chromaticity of K4-homeomorphs, by which some new results are obtained.     

Dn补图的色唯一性

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

若干图簇的伴随多项式的因式分解及色性分析

我们通过研究图的伴随多项式的因式分解,给出了证明非色唯一图的一种新方法,同时得到若干图簇的色等价图的结构定理.     

研究K4-同胚图K4(α,1,1,δ,ε,η)色性的一个引理

主要介绍了一个引理，这个引理奠定了K4－同胚图K4（α，1，1，δ，ε，η）色性研究的基础。     

路的补图的色唯一性

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

伴随多项式的根与色等价图的刻画

文[2]给出了不含三角形图伴随多项式根的内插性质,本文研究了含三角形图的伴随多项式根的性质,在此基础上完整地刻画了■的色等价图,且给出这类图色唯一的充要条件.Cti表示有ti个顶点的圈;Dn表示Pn-2的一个1度点粘接下来K3的一个点得到的图.     

图的伴随多项式基于挖补定理的因式分解及其色性分析

通过研究H_t~Γ及H_t~L类图簇的伴随多项式的因式分解,证明了两类图的补图的色等价图的结构性质和非色唯一性.