A zero-free interval for chromatic polynomials of graphs with 3-leaf spanning trees

详细信息    查看全文

• 作者：Thomas Perrett ^{tper@dtu.dk" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Chromatic polynomial ; Zero-free interval ; Spanning tree ; Splitting-closed
• 刊名：Discrete Mathematics
• 出版年：2016
• 出版时间：6 November 2016
• 年：2016
• 卷：339
• 期：11
• 页码：2706-2714
• 全文大小：441 K

文摘

It is proved that if G$G$ is a graph containing a spanning tree with at most three leaves, then the chromatic polynomial of G$G$ has no roots in the interval (1,t₁]$(1,t_1]$, where t₁≈1.2904$t_1\approx 1.2904$ is the smallest real root of the polynomial (t−2)⁶+4(t−1)²(t−2)³−(t−1)⁴${(t-2)}^6+4{(t-1)}^2{(t-2)}^3-{(t-1)}^4$. We also construct a family of graphs containing such spanning trees with chromatic roots converging to t₁$t_1$ from above. We employ the Whitney 2-switch operation to manage the analysis of an infinite class of chromatic polynomials.