Non-chordal graphs having integral-root chromatic polynomials. II (Q1348126): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 04:01, 5 March 2024
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
chordal graphs
0 references
chordless cycles
0 references
chromatic polynomial
0 references
integer roots
0 references