Dn补图的色唯一性

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

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

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

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

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

圈并的补图的色唯一性的一个结果

本文证明了 :如果对每个 i∈ {1 ,2 ,… ,t},都有 ni≥ 5 ,且 ni是正整数 ,那么 Cn1∪ Cn2 ∪…∪ Cnt是色唯一的     

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

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

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

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

圈和Dn图的补图的色唯一性

圈和Ｄｎ图的补图的色唯一性王守中刘儒英（青海师范大学数学系，西宁８１０００８）关键词图，色多项式，色唯一性．分类号ＡＭＳ（１９９１）０５Ｃ／ＣＣＬＯ１５７．５用Ｐｎ和Ｃｎ表示有ｎ个顶点的路和圈．用Ｄｎ表示把Ｋ３的一个顶点与Ｐｎ－２的一个一度顶点重迭后...     

一类树并的补图的色唯一性

彻底解决了一类不可约树并的补图是色唯一的 ,并得到了一些图的伴随多项式的最小根的重要规律 .     

图Kn—E（k0P3（∪↑r↓i=1kiPqi—1））的色唯一性

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

与lK1∪(∪Cui)的补图有相同色划分的图

本文利用色多项式的性质讨论了lK1∪(∪Cui)的补图的色等价划分，从而在ui≠4k 2的条件下完全刻画了与此类图具有相同色等价划分的图。     

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     

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

我们通过研究Γ-型图簇的伴随多项式的因式分解,证明了这些图簇的补图的色等价图的结构性质和非色唯一性.     

单圈图的伴随多项式的极小根（英文）

引入伴随多项式是为了从补图的角度研究色多形式,图的伴随多项式的极小根可用于判定色等价图.β（G）表示图G的伴随多项式的极小根.n表示n个顶点的单圈图的集合.分别确定了具有max{β（G）｜G∈Ωn}和min{β（G）｜G∈Ωn}的所有单圈图.     

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~(GS*)类图簇的伴随多项式的因式分解及其色性

通过研究SGS*类图簇的伴随多项式的因式分解,证明了这类图簇的补图的色等价图的结构特征.     

关于K4同胚图色唯一性的几个新结果

本文证得:如果i,j,k,l,m,n中有四个数相等,而另外二个数不小于此数,则K_4(i,j,k,l,m,n)是色唯一的.此外,我们还得到了另外两族具有色唯一性的K_4同胚图.