Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-23T14:00:47.534Z Has data issue: false hasContentIssue false
  • English
  • Français

Two Results on Real Zeros of Chromatic Polynomials

Published online by Cambridge University Press:  03 November 2004

F. M. DONG  and
K. M. KOH
F. M. DONG
Affiliation:
Mathematics and Mathematics Education, National Institute of Education, Nanyang Technological University, Singapore 637616 (e-mail: [email protected])
K. M. KOH
Affiliation:
Department of Mathematics, National University of Singapore, Singapore 117543 (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

This note presents two results on real zeros of chromatic polynomials. The first result states that if $G$ is a graph containing a $q$-tree as a spanning subgraph, then the chromatic polynomial $P(G,\lambda)$ of $G$ has no non-integer zeros in the interval $(0,q)$. Sokal conjectured that for any graph $G$ and any real $\lambda>\Delta(G)$, $P(G,\lambda)>0$. Our second result confirms that it is true if $\Delta(G)\ge \lfloor n/3\rfloor -1$, where $n$ is the order of $G$.

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 13 , Issue 6 , November 2004 , pp. 809 - 813
Copyright
2004 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)