Hostname: page-component-74656f9884-j7cmm Total loading time: 0 Render date: 2026-11-09T21:26:17.216Z Has data issue: false hasContentIssue false

Two Results on Real Zeros of Chromatic Polynomials

Published online by Cambridge University Press:  03 November 2004

F. M. DONG
Affiliation:
Mathematics and Mathematics Education, National Institute of Education, Nanyang Technological University, Singapore 637616 (e-mail: fmdong@nie.edu.sg)
K. M. KOH
Affiliation:
Department of Mathematics, National University of Singapore, Singapore 117543 (e-mail: matkohkm@nus.edu.sg)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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$.

Information

Type
Paper
Copyright
2004 Cambridge University Press