Please use this identifier to cite or link to this item:
https://scholarbank.nus.edu.sg/handle/10635/103610
DC Field | Value | |
---|---|---|
dc.title | Non-chordal graphs having integral-root chromatic polynomials II | |
dc.contributor.author | Dong, P.M. | |
dc.contributor.author | Teo, K.L. | |
dc.contributor.author | Koh, K.M. | |
dc.contributor.author | Hendy, M.D. | |
dc.date.accessioned | 2014-10-28T02:39:15Z | |
dc.date.available | 2014-10-28T02:39:15Z | |
dc.date.issued | 2002-02-28 | |
dc.identifier.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. | |
dc.identifier.issn | 0012365X | |
dc.identifier.uri | http://scholarbank.nus.edu.sg/handle/10635/103610 | |
dc.description.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. | |
dc.source | Scopus | |
dc.subject | Chordal graphs | |
dc.subject | Chromatic polynomials | |
dc.type | Article | |
dc.contributor.department | MATHEMATICS | |
dc.description.sourcetitle | Discrete Mathematics | |
dc.description.volume | 245 | |
dc.description.issue | 1-3 | |
dc.description.page | 247-253 | |
dc.description.coden | DSMHA | |
dc.identifier.isiut | NOT_IN_WOS | |
Appears in Collections: | Staff Publications |
Show simple item record
Files in This Item:
There are no files associated with this item.
Google ScholarTM
Check
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.