On graphs having no chromatic zeros in (1, 2)

Abstract

For a graph G of order n ≥ 2, an ordering (x1,x 2,...,xn) of the vertices in G is called a double-link ordering of G if x1x2 ∈ E(G) and xi has at least two neighbors in {x1, x2,...,xi-1} for all i = 3,4,...,n. This paper shows that certain graphs possessing a kind of double-link ordering have no chromatic zeros in the interval (1,2). This result implies that all graphs with a 2-tree as a spanning subgraph, certain graphs with a Hamiltonian path, all complete t-partite graphs, where t ≥ 3, and all (v(G) - Δ(G) + 1)-connected graphs G have no chromatic zeros in the interval (1,2). © 2006 Society for Industrial and Applied Mathematics.