共查询到18条相似文献,搜索用时 46 毫秒
1.
张树生 《数学的实践与认识》2001,31(6):675-679
本文证明了 :如果对每个 i∈ {1 ,2 ,… ,t},都有 ni≥ 5 ,且 ni是正整数 ,那么 Cn1∪ Cn2 ∪…∪ Cnt是色唯一的 相似文献
2.
讨论了形如kCRUrPR的一类图的补图的色性.在一定的条件下证明了这类图是色唯一的.本文推广了文[1]的结果. 相似文献
3.
圈和Dn图的补图的色唯一性 总被引:37,自引:0,他引:37
圈和Dn图的补图的色唯一性王守中刘儒英(青海师范大学数学系,西宁810008)关键词图,色多项式,色唯一性.分类号AMS(1991)05C/CCLO157.5用Pn和Cn表示有n个顶点的路和圈.用Dn表示把K3的一个顶点与Pn-2的一个一度顶点重迭后... 相似文献
4.
利用伴随多项式来讨论图的着色唯一性是近二十年来出现的新方法.用Pn表示有n个顶点的路.Dn表示把K3的一个顶点与Pn-2的一个一度顶点重迭后得到的图.该文推广了相关文献的结论,得到D^-n色唯一当且仅当n≠4且n≠8.彻底解决了这类图的色性. 相似文献
5.
6.
7.
本文用全新的方法证明了两类图的色多项式唯一性,推广了Beatrice Loe-rine关于广义θ-图的色多项式唯一性的结论。 相似文献
8.
9.
10.
11.
关于K4同胚图色唯一性的几个新结果 总被引:4,自引:0,他引:4
本文证得:如果i,j,k,l,m,n中有四个数相等,而另外二个数不小于此数,则K_4(i,j,k,l,m,n)是色唯一的.此外,我们还得到了另外两族具有色唯一性的K_4同胚图. 相似文献
12.
用k4(a ,b ,c ,d ,e,f)表示k4 同胚图 ,其中a ,b ,c ,d ,e,f分别表示度为 3的顶点间的道路的长 .本文主要研究了两类k4 同胚图的色唯一性 ,同时得到了几族新的不是色唯一的k4 同胚图 相似文献
13.
ZHANG Shu-min 《数学季刊》2004,(2)
In the paper, we prove that the complement of Tm(1,4,m - 6)(m > 10) is chromatically unique if and only if m ≠5k(k ≥ 2). 相似文献
14.
15.
Some necessary conditions on a graph which has the same chromatic polynomial as the complete tripartite graph Km,n,r are developed. Using these, we obtain the chromatic equivalence classes for Km,n,n (where 1≤m≤n) and Km1,m2,m3 (where |mi−mj|≤3). In particular, it is shown that (i) Km,n,n (where 2≤m≤n) and (ii) Km1,m2,m3 (where |mi−mj|≤3, 2≤mi,i=1,2,3) are uniquely determined by their chromatic polynomials. The result (i), proved earlier by Liu et al. [R.Y. Liu, H.X. Zhao, C.Y. Ye, A complete solution to a conjecture on chromatic uniqueness of complete tripartite graphs, Discrete Math. 289 (2004) 175-179], answers a conjecture (raised in [G.L. Chia, B.H. Goh, K.M. Koh, The chromaticity of some families of complete tripartite graphs (In Honour of Prof. Roberto W. Frucht), Sci. Ser. A (1988) 27-37 (special issue)]) in the affirmative, while result (ii) extends a result of Zou [H.W. Zou, On the chromatic uniqueness of complete tripartite graphs Kn1,n2,n3 J. Systems Sci. Math. Sci. 20 (2000) 181-186]. 相似文献
16.
Let P(G,λ) be the chromatic polynomial of a simple graph G. A graph G is chromatically unique if for any simple graph H, P(H,λ) = P(G,λ) implies that H is isomorphic to G. Many sufficient conditions guaranteeing that some certain complete tripartite graphs are chromatically unique were obtained by many scholars. Especially, in 2003, Zou Hui-wen showed that if n 31m2 + 31k2 + 31mk+ 31m? 31k+ 32√m2 + k2 + mk, where n,k and m are non-negative integers, then the complete tripartite graph K(n - m,n,n + k) is chromatically unique (or simply χ-unique). In this paper, we prove that for any non-negative integers n,m and k, where m ≥ 2 and k ≥ 0, if n ≥ 31m2 + 31k2 + 31mk + 31m - 31k + 43, then the complete tripartite graph K(n - m,n,n + k) is χ-unique, which is an improvement on Zou Hui-wen's result in the case m ≥ 2 and k ≥ 0. Furthermore, we present a related conjecture. 相似文献
17.
Carsten Thomassen 《Discrete Mathematics》2006,306(23):3145-3153
We prove that, for every fixed surface S, there exists a largest positive constant c such that every 5-colorable graph with n vertices on S has at least c·2n distinct 5-colorings. This is best possible in the sense that, for each sufficiently large natural number n, there is a graph with n vertices on S that has precisely c·2n distinct 5-colorings. For the sphere the constant c is , and for each other surface, it is a finite problem to determine c. There is an analogous result for k-colorings for each natural number k>5. 相似文献