Non-chordal graphs having integral-root chromatic polynomials. II (Q1348126)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Non-chordal graphs having integral-root chromatic polynomials. II
scientific article

    Statements

    Non-chordal graphs having integral-root chromatic polynomials. II (English)
    0 references
    15 May 2002
    0 references
    \textit{I. G. Dmitriev} [Metody Discretn. Anal. 34, 3-7 (1980; Zbl 0459.05037)] asked in 1980 if for any integer \(p\geq 4\), there exists a graph with chordless cycles of length \(p\) whose chromatic polynomial has only integer roots. The authors construct a family of graphs in which all chordless cycles are of length \(p\) for any integer \(p\geq 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. This paper extends Dong and Koh's result for \(p=5\) and answers the question affirmatively for \(p= 6\) and \(7\); see \textit{F. M. Dong} and \textit{K. M. Koh} [Non-chordal graphs having integral-root chromatic polynomials, Bull. Inst. Comb. Appl. 22, 67-77 (1998; Zbl 0894.05014)].
    0 references
    0 references
    chordal graphs
    0 references
    chordless cycles
    0 references
    chromatic polynomial
    0 references
    integer roots
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references