Please use this identifier to cite or link to this item:
Title: Non-chordal graphs having integral-root chromatic polynomials II
Authors: Dong, P.M.
Teo, K.L.
Koh, K.M. 
Hendy, M.D.
Keywords: Chordal graphs
Chromatic polynomials
Issue Date: 28-Feb-2002
Citation: Dong, P.M.,Teo, K.L.,Koh, K.M.,Hendy, M.D. (2002-02-28). Non-chordal graphs having integral-root chromatic polynomials II. Discrete Mathematics 245 (1-3) : 247-253. ScholarBank@NUS Repository.
Abstract: It is known that the chromatic polynomial of any chordal graph has only integer roots. However, there also exist non-chordal graphs whose chromatic polynomials have only integer roots. Dmitriev asked in 1980 if for any integer p > 4, there exists a graph with chordless cycles of length p whose chromatic polynomial has only integer roots. This question has been given positive answers by Dong and Koh for p = 4 and p = 5. In this paper, we construct a family of graphs in which all chordless cycles are of length p for any integer p ≥ 4. It is shown that the chromatic polynomial of such a graph has only integer roots iff a polynomial of degree p - 1 has only integer roots. By this result, this paper extends Dong and Koh's result for p = 5 and answer the question affirmatively for p = 6 and 7. © 2002 Elsevier Science B.V. All rights reserved.
Source Title: Discrete Mathematics
ISSN: 0012365X
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

checked on Apr 20, 2018

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.