A new recursive vertex-deleting formula for the computation of the chromatic polynomial of a graph is obtained in this paper. This algorithm is not only a good tool for further studying chromatic polynomials but also ...A new recursive vertex-deleting formula for the computation of the chromatic polynomial of a graph is obtained in this paper. This algorithm is not only a good tool for further studying chromatic polynomials but also the fastest among all the algorithms for the computation of chromatic polynomials.展开更多
By means of the chromatic polynomials, this paper provided a necessary and sufficient condition for the graph G being a mono-cycle graph（the Theorem 1）, a first class hi-cycle graph and a second class bicycle graph...By means of the chromatic polynomials, this paper provided a necessary and sufficient condition for the graph G being a mono-cycle graph（the Theorem 1）, a first class hi-cycle graph and a second class bicycle graph（the Theorem 2）, respectively.展开更多
In this paper, a new method has been used to calculate the chromatic polynomials of graphs. In particular, the chromatic polynomials of complements of all wheels with any missing consecutive spokes are given.
Let Sn be the star with n vertices, and let G be any connected graph with p vertices. We denote by Eτp＋（r-1）^G（i） the graph obtained from Sr and rG by coinciding the i-th vertex of G with the vertex of degree r ...Let Sn be the star with n vertices, and let G be any connected graph with p vertices. We denote by Eτp＋（r-1）^G（i） the graph obtained from Sr and rG by coinciding the i-th vertex of G with the vertex of degree r - 1 of S,, while the i-th vertex of each component of （r - 1）G be adjacented to r - 1 vertices of degree 1 of St, respectively. By applying the properties of adjoint polynomials, We prove that factorization theorem of adjoint polynomials of kinds of graphs Eτp＋（r-1）^G（i）∪（r - 1）K1 （1 ≤i≤p）. Furthermore, we obtain structure characteristics of chromatically equivalent graphs of their complements.展开更多
In this paper,a new method is used to calculate the chromatic polynomials of graphs.The chro-matic polynomials of the complements of a wheel and a fan are determined.Furthermore,the adjoint polynomialsof F_n with n ve...In this paper,a new method is used to calculate the chromatic polynomials of graphs.The chro-matic polynomials of the complements of a wheel and a fan are determined.Furthermore,the adjoint polynomialsof F_n with n vertices are obtained.This supports a conjecture put forward by R.Y.Liu et al.展开更多
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 q be a positive integer.The graphs,called the q-trees are defined by recursion:the smallest q-tree is the complete graph K_q with q vertices,and a q-tree with n+1 vertices where n≥q is obtained by adding a new ve...Let q be a positive integer.The graphs,called the q-trees are defined by recursion:the smallest q-tree is the complete graph K_q with q vertices,and a q-tree with n+1 vertices where n≥q is obtained by adding a new vertex adjacent to each of q arbitrarily selected but mutually adjacent vertices of q-tree with n vertices.Obviously,1-trees are the graphs which are generally called trees.In this paper,it is proved that for any positive integer q,q-tree is reconstructible.展开更多
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.展开更多
In this paper, we are concerned with the minimum real root of the adjoint polynomial of the connected graph G with cut-vertex u, in which G - u contains paths, circles or Dn components. Here Dn is the graph obtained f...In this paper, we are concerned with the minimum real root of the adjoint polynomial of the connected graph G with cut-vertex u, in which G - u contains paths, circles or Dn components. Here Dn is the graph obtained from K3 and path Pn-2 by identifying a vertex of K3 with an end-vertex of Pn-2. Some relevant ordering relations are obtained. This extends several previous results on the minimum roots of the adjoint polynomials of graphs.展开更多
基金This research is partially supported by NNSF of China.
文摘A new recursive vertex-deleting formula for the computation of the chromatic polynomial of a graph is obtained in this paper. This algorithm is not only a good tool for further studying chromatic polynomials but also the fastest among all the algorithms for the computation of chromatic polynomials.
基金Supported by the NNSF of China(10861009)Supported by the Ministry of Education Science and Technology Item of China(206156)
文摘By means of the chromatic polynomials, this paper provided a necessary and sufficient condition for the graph G being a mono-cycle graph（the Theorem 1）, a first class hi-cycle graph and a second class bicycle graph（the Theorem 2）, respectively.
基金Supported by National Natural Science Found of China(1027101710271048)
文摘In this paper, a new method has been used to calculate the chromatic polynomials of graphs. In particular, the chromatic polynomials of complements of all wheels with any missing consecutive spokes are given.
文摘Let Sn be the star with n vertices, and let G be any connected graph with p vertices. We denote by Eτp＋（r-1）^G（i） the graph obtained from Sr and rG by coinciding the i-th vertex of G with the vertex of degree r - 1 of S,, while the i-th vertex of each component of （r - 1）G be adjacented to r - 1 vertices of degree 1 of St, respectively. By applying the properties of adjoint polynomials, We prove that factorization theorem of adjoint polynomials of kinds of graphs Eτp＋（r-1）^G（i）∪（r - 1）K1 （1 ≤i≤p）. Furthermore, we obtain structure characteristics of chromatically equivalent graphs of their complements.
基金Supported by Foundation of Beijing Jiaotong University and by the National Natural Science Foundation of China (No.10271017,No.60373030) and Beijing National Science Foundation (No.1012003)
文摘In this paper,a new method is used to calculate the chromatic polynomials of graphs.The chro-matic polynomials of the complements of a wheel and a fan are determined.Furthermore,the adjoint polynomialsof F_n with n vertices are obtained.This supports a conjecture put forward by R.Y.Liu et al.
基金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 q be a positive integer.The graphs,called the q-trees are defined by recursion:the smallest q-tree is the complete graph K_q with q vertices,and a q-tree with n+1 vertices where n≥q is obtained by adding a new vertex adjacent to each of q arbitrarily selected but mutually adjacent vertices of q-tree with n vertices.Obviously,1-trees are the graphs which are generally called trees.In this paper,it is proved that for any positive integer q,q-tree is reconstructible.
文摘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.
基金the National Natural Science Foundation of China (Nos.10461009 10641003)the Key Project of Chinese Ministry of Education (No.206158)
文摘In this paper, we are concerned with the minimum real root of the adjoint polynomial of the connected graph G with cut-vertex u, in which G - u contains paths, circles or Dn components. Here Dn is the graph obtained from K3 and path Pn-2 by identifying a vertex of K3 with an end-vertex of Pn-2. Some relevant ordering relations are obtained. This extends several previous results on the minimum roots of the adjoint polynomials of graphs.
