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.
The 224 non-chordal graphs on less than 10 vertices whose chromatic polynomials have no complex roots / O. D'Antona, C. Mereghetti, F. Zamparini. - In: DISCRETE MATHEMATICS. - ISSN 0012-365X. - 226:1-3(2001), pp. 387-396.
The 224 non-chordal graphs on less than 10 vertices whose chromatic polynomials have no complex roots
O. D'Antona
;C. MereghettiSecondo
;
2001
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.File | Dimensione | Formato | |
---|---|---|---|
pubblicato.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
219.11 kB
Formato
Adobe PDF
|
219.11 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.