With its comprehensive application in network information engineering （e. g. dynamic spectrum allocation under different distance constraints ） and in network combination optimization （e. g. safe storage of deleter...With its comprehensive application in network information engineering （e. g. dynamic spectrum allocation under different distance constraints ） and in network combination optimization （e. g. safe storage of deleterious materials）, the graphs＇ cloring theory and chromatic uniqueness theory have been the forward position of graph theory research. The later concerns the equivalent classification of graphs with their color polynomials and the determination of uniqueness of some equivalent classification under isomorphism. In this paper, by introducing the concept of chromatic normality and comparing the number of partitions of two chromatically equivalent graphs, a general numerical condition guarenteeing that bipartite graphs K （ m, n） - A （A belong to E（K （m, n） ） and ｜ A ｜≥ 2） is chromatically unique was obtained and a lot of chromatic uniqueness graphs of bipartite graphs K（m, n） - A were determined. The results obtained in this paper were general. And the results cover and extend the majority of the relevant results obtained within the world.展开更多
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.
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.展开更多
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.展开更多
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.展开更多
基金Natural Science Foundation of Fujian, China (No.S0650011)
文摘With its comprehensive application in network information engineering （e. g. dynamic spectrum allocation under different distance constraints ） and in network combination optimization （e. g. safe storage of deleterious materials）, the graphs＇ cloring theory and chromatic uniqueness theory have been the forward position of graph theory research. The later concerns the equivalent classification of graphs with their color polynomials and the determination of uniqueness of some equivalent classification under isomorphism. In this paper, by introducing the concept of chromatic normality and comparing the number of partitions of two chromatically equivalent graphs, a general numerical condition guarenteeing that bipartite graphs K （ m, n） - A （A belong to E（K （m, n） ） and ｜ A ｜≥ 2） is chromatically unique was obtained and a lot of chromatic uniqueness graphs of bipartite graphs K（m, n） - A were determined. The results obtained in this paper were general. And the results cover and extend the majority of the relevant results obtained within the world.
文摘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.
基金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.
文摘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.
文摘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.
