Clique roots of K4-free chordal graphs

Abstract

The clique polynomial C(G, x) of a finite, simple and undirected graph G = (V, E) is defined as the ordinary generating function of the number of complete subgraphs of G. A real root of C(G, x) is called a clique root of the graph G. Hajiabolhasan and Mehrabadi showed that every simple graph G has at least a clique root in the interval [ − 1, 0). Moreover, they showed that the class of triangle-free graphs has only clique roots. In this paper, we extend their result by showing that the class of K4-free chordal graphs has also only clique roots. In particular, we show that this class has always a clique root − 1. We conclude our paper with some interesting open questions and conjectures.

Keywords

• clique polynomial, clique root, chordal graph, clique decomposition