Let P（G,A） 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 com...Let P（G,A） 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 〉 k2/4 ＋ i ＋ 1.展开更多
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 guarantee...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 〉 1/3m2 ＋ 3/1k2 ＋ 3/1mk＋ 1/3m-1/3k＋ 3/2√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 ≥ 3/1m2 ＋ 3/1k2 ＋ 3/1mk ＋ 3/1m - 3/1k ＋ 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.展开更多
For a graph G,P(G,λ)denotes the chromatic polynomial of G.Two graphs G and H are said to be chromatically equivalent,denoted by G～H,if P(G,λ)=p(H,λ).Let [G]={H|H～G}.If [G]={G},then G is said to be chromaticall...For a graph G,P(G,λ)denotes the chromatic polynomial of G.Two graphs G and H are said to be chromatically equivalent,denoted by G～H,if P(G,λ)=p(H,λ).Let [G]={H|H～G}.If [G]={G},then G is said to be chromatically unique.For a complete 5 partite graph G with 5n vertices, define θ(G)=(α(G,6)-2 n+1 -2 n-1 + 5)/2 n-2 ,where α(G,6) denotes the number of 6 independent partition s of G.In this paper, the authors show that θ(G)≥0 and determine all g raphs with θ(G)=0,1,2,5/2,7/2,4,17/4.By using these results the chromaticity of 5 partite graphs of the form G-S with θ(G)=0,1,2,5/2,7/2,4,17/4 is inve stigated,where S is a set of edges of G.Many new chromatically unique 5 partite graphs are obtained.展开更多
It is shown that K 4(i,j,l,k,m,n) is chromatically unique if three numbers among i,j,l,k,m,n have the same value and the other three numbers are not equal but larger than that value.
Let P（G, λ） be the chromatic polynomial of a graph G. Two graphs G and H are said to be chromatically equivalent, denoted G N H, if P（G, λ） = P（H, λ）. We write [G] = {HIH - G}. If [G] = {G}, then G is said to...Let P（G, λ） be the chromatic polynomial of a graph G. Two graphs G and H are said to be chromatically equivalent, denoted G N H, if P（G, λ） = P（H, λ）. We write [G] = {HIH - G}. If [G] = {G}, then G is said to be chromatically unique. In this paper, we first characterize certain complete 6-partite graphs with 6rid＋1 vertices according to the number of 7-independent partitions of G. Using these results, we investigate the chromaticity of G with certain star or matching deleted. As a by-product, many new families of chromatically unique complete 6-partite graphs with certain star or matching deleted are obtained.展开更多
设G是一个图,P(G,λ)是G的色多项式.若P(G,λ)=P(H,λ),则称G和H是色等价的,简单地用G～H表示.令[G]={H|H～G}.若[G]={G},称G是色唯一的.用G=K(n1,n2,n3,n4)表示完全四部图且2 n1 n2 n3 n4,得到了[G] {K(x,y,z,w)-S|x+y+z+w=n1+n2+n3+n4...设G是一个图,P(G,λ)是G的色多项式.若P(G,λ)=P(H,λ),则称G和H是色等价的,简单地用G～H表示.令[G]={H|H～G}.若[G]={G},称G是色唯一的.用G=K(n1,n2,n3,n4)表示完全四部图且2 n1 n2 n3 n4,得到了[G] {K(x,y,z,w)-S|x+y+z+w=n1+n2+n3+n4,1 x y z w n4-1,或1 x y z n3-1和w=n4}∪{G},其中S是K(x,y,z,w)的某s条边组成的集合且K(x,y,z,w)-S表示从K(x,y,z,w)中删去S中所有边得到的图.从而证明了当n k+2,k 2时,K(n-k,n,n,n)是色唯一的.展开更多
文摘Let P（G,A） 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 〉 k2/4 ＋ i ＋ 1.
基金Supported by the National Natural Science Foundation of China (Grant No.10771091)the Science and Research Project of the Education Department of Gansu Province (Grant No.0501-02)
文摘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 〉 1/3m2 ＋ 3/1k2 ＋ 3/1mk＋ 1/3m-1/3k＋ 3/2√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 ≥ 3/1m2 ＋ 3/1k2 ＋ 3/1mk ＋ 3/1m - 3/1k ＋ 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.
基金Supported by the National Natural Science Foundation of China (1 0 0 61 0 0 3) and the ScienceFoundation of the State Education Ministry of China
文摘For a graph G,P(G,λ)denotes the chromatic polynomial of G.Two graphs G and H are said to be chromatically equivalent,denoted by G～H,if P(G,λ)=p(H,λ).Let [G]={H|H～G}.If [G]={G},then G is said to be chromatically unique.For a complete 5 partite graph G with 5n vertices, define θ(G)=(α(G,6)-2 n+1 -2 n-1 + 5)/2 n-2 ,where α(G,6) denotes the number of 6 independent partition s of G.In this paper, the authors show that θ(G)≥0 and determine all g raphs with θ(G)=0,1,2,5/2,7/2,4,17/4.By using these results the chromaticity of 5 partite graphs of the form G-S with θ(G)=0,1,2,5/2,7/2,4,17/4 is inve stigated,where S is a set of edges of G.Many new chromatically unique 5 partite graphs are obtained.
文摘It is shown that K 4(i,j,l,k,m,n) is chromatically unique if three numbers among i,j,l,k,m,n have the same value and the other three numbers are not equal but larger than that value.
文摘Let P（G, λ） be the chromatic polynomial of a graph G. Two graphs G and H are said to be chromatically equivalent, denoted G N H, if P（G, λ） = P（H, λ）. We write [G] = {HIH - G}. If [G] = {G}, then G is said to be chromatically unique. In this paper, we first characterize certain complete 6-partite graphs with 6rid＋1 vertices according to the number of 7-independent partitions of G. Using these results, we investigate the chromaticity of G with certain star or matching deleted. As a by-product, many new families of chromatically unique complete 6-partite graphs with certain star or matching deleted are obtained.
文摘设G是一个图,P(G,λ)是G的色多项式.若P(G,λ)=P(H,λ),则称G和H是色等价的,简单地用G～H表示.令[G]={H|H～G}.若[G]={G},称G是色唯一的.用G=K(n1,n2,n3,n4)表示完全四部图且2 n1 n2 n3 n4,得到了[G] {K(x,y,z,w)-S|x+y+z+w=n1+n2+n3+n4,1 x y z w n4-1,或1 x y z n3-1和w=n4}∪{G},其中S是K(x,y,z,w)的某s条边组成的集合且K(x,y,z,w)-S表示从K(x,y,z,w)中删去S中所有边得到的图.从而证明了当n k+2,k 2时,K(n-k,n,n,n)是色唯一的.
