On the minimum real roots of the σ-polynomials and chromatic uniqueness of graphs

详细信息    查看全文

• 作者：Zhao ; Haixing ; Li ; Xueliang ; Zhang ; Shenggui ; Liu ; Ruying
• 关键词：05C15 ; 05C60 ; Chromatically unique ; σ ; -Polynomials ; Adjoint polynomials ; Adjointly unique ; Minimum real roots
• 刊名：Discrete Mathematics
• 出版年：2004
• 出版时间：April 28, 2004
• 年：2004
• 卷：281
• 期：1-3
• 页码：277-294
• 全文大小：301 K

文摘

Let β(G) denote the minimum real root of the σ-polynomial of the complement of a graph G and δ(G) the minimum degree of G. In this paper, we give a characterization of all connected graphs G with β(G)≥−4. Using these results, we establish a sufficient and necessary condition for a graph G with p vertices and δ(G)≥p−3, to be chromatically unique. Many previously known results are generalized. As a byproduct, a problem of Du (Discrete Math. 162 (1996) 109–125) and a conjecture of Liu (Discrete Math. 172 (1997) 85–92) are confirmed.