Chromatic roots and hamiltonian paths

Carsten Thomassen

doi:10.1006/jctb.2000.1976

Chromatic roots and hamiltonian paths

Research output: Contribution to journal › Journal article › Research › peer-review

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.

Original language	English
Journal	Journal of Combinatorial Theory. Series B
Volume	80
Issue number	2
Pages (from-to)	218-224
ISSN	0095-8956
DOIs	https://doi.org/10.1006/jctb.2000.1976
Publication status	Published - Nov 2000

Access to Document

10.1006/jctb.2000.1976

Fingerprint Dive into the research topics of 'Chromatic roots and hamiltonian paths'. Together they form a unique fingerprint.

Cite this

@article{524da18bc66a42328159f966efb4c6f5,

title = "Chromatic roots and hamiltonian paths",

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 tot(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. ",

author = "Carsten Thomassen",

year = "2000",

month = nov,

doi = "10.1006/jctb.2000.1976",

language = "English",

volume = "80",

pages = "218--224",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press",

number = "2",

}

TY - JOUR

T1 - Chromatic roots and hamiltonian paths

AU - Thomassen, Carsten

PY - 2000/11

Y1 - 2000/11

N2 - 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 tot(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.

AB - 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 tot(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.

U2 - 10.1006/jctb.2000.1976

DO - 10.1006/jctb.2000.1976

M3 - Journal article

VL - 80

SP - 218

EP - 224

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

SN - 0095-8956

IS - 2

ER -