Language:   Search:   Contact
Zentralblatt MATH has released its new interface!
For an improved author identification, see the new author database of ZBMATH.

Query:
Fill in the form and click »Search«...
Format:
Display: entries per page entries
Zbl 0794.05030
Jackson, Bill
A zero-free interval for chromatic polynomials of graphs.
(English)
[J] Comb. Probab. Comput. 2, No.3, 325-336 (1993). ISSN 0963-5483; ISSN 1469-2163/e

Let $G$ be a graph and $P(G,t)$ be the chromatic polynomial of $G$. It is known that $P(G,t)$ has no zeros in the intervals $(-\infty,0)$, $(0,1)$ and $(2,\alpha)$, where $\alpha\approx 2.5466$ is the smallest non- integer real zero of the chromatic polynomial of the octahedron. The main result of this interesting paper is the following: Let $G$ be a connected, simple graph on $n$ vertices with $n\ge 2$ and let $b$ be the number of blocks of $G$. Then $P(G,t)$ is non-zero with $\text{sign} (- 1)\sp{n+b+1}$ for all $t\in (1,32/27]$. Moreover, given any real $\varepsilon>0$, there exists a graph whose chromatic polynomial has a zero in $(32/27,(32/27)+ \varepsilon)$. The following conjecture is made: Let $G$ be a 3-connected non-bipartite graph. Then $P(G,t)$ has no zeros in the interval $(1,2)$.
[I.Tomescu (Bucureşti)]
MSC 2000:
*05C15 Chromatic theory of graphs and maps

Keywords: zero-free interval; generalized triangle; chromatic polynomial; blocks

Highlights
Master Server