Abstract
We present a new connection between colorings and hamiltonian paths: If the chromatic polynomial of a graph has a noninteger root less than or equal to
t(n) = 2/3 + 1/3 (3)root (26 + 6 root (33)) + 1/3 (3)root (26 - 6 root (33)) = 1.29559....
then the graph has no hamiltonian path. This result is best possible in the sense that ii becomes false if t(0) is replaced by any larger number. (C) 2000 Academic Press.
t(n) = 2/3 + 1/3 (3)root (26 + 6 root (33)) + 1/3 (3)root (26 - 6 root (33)) = 1.29559....
then the graph has no hamiltonian path. This result is best possible in the sense that ii becomes false if t(0) is replaced by any larger number. (C) 2000 Academic Press.
| Original language | English |
|---|---|
| Journal | Journal of Combinatorial Theory. Series B |
| Volume | 80 |
| Issue number | 2 |
| Pages (from-to) | 218-224 |
| ISSN | 0095-8956 |
| DOIs | |
| Publication status | Published - Nov 2000 |