On Graphs Having No Chromatic Zeros in (1,2)
Fengming Dong, K.M. Koh · SIAM Journal on Discrete Mathematics · 2006
For a graph G of order $n\ge 2$, an ordering $(x_1,x_2,\ldots, x_n)$ of the vertices in G is called a double‐link ordering of G if $x_1x_2\in E(G)$ and $x_i$ has at least two neighbors in $\{x_1,x_2,\ldots,x_{i-1}\}$ for all $i=3,4,\ldots,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\ge 3$, and all $(v(G)-\Delta(G)+1)$‐connected graphs G have no chromatic zeros in the interval (1,2).