Advanced Search

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

Cited in: Zbl 1210.05062 Zbl 1199.05103 Zbl 1139.05019 Zbl 0919.05011 Zbl 0887.05020

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]