Title of article :
The 224 non-chordal graphs on less than 10 vertices whose chromatic polynomials have no complex roots
Author/Authors :
Ottavio M. DʹAntona، نويسنده , , Carlo Mereghetti، نويسنده , , Fabio Zamparini، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2001
Pages :
10
From page :
387
To page :
396
Abstract :
We show that all non-chordal graphs up to 9 vertices whose chromatic polynomials have no complex roots can be generated by applying a (sequence of) few operations to a small clique. These operations are the chromatic expansion (connecting a new vertex to every vertex of the given graph), the pyramid (connecting a new vertex to a clique of the given graph), and two new operations — here called bipyramid and tripyramid — that generalize the previous one. We also exhibit the smallest non-chordal graph whose chromatic polynomial has only integer and irrational roots, the smallest graph with a chordless circuit of length 5 whose chromatic polynomial has no complex roots and introduce some infinite families of non-chordal graphs whose chromatic polynomials have no complex roots.
Keywords :
Pyramidal operations , Non-chordal graphs , Chromatic polynomial
Journal title :
Discrete Mathematics
Serial Year :
2001
Journal title :
Discrete Mathematics
Record number :
949562
Link To Document :
بازگشت