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. Mereghetti
Secondo
;
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.
Chromatic polynomial; Non-chordal graphs; Pyramidal operations
Settore INF/01 - Informatica
2001
Article (author)
File in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/179168
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 22
social impact