Clique roots of K4-free chordal graphs

Hossein Teimoori Faal


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.


clique polynomial, clique root, chordal graph, clique decomposition

Full Text:




J.A. Bondy and U.S.R. Murty, Graph theory with applications, American Elsevier Publishing Co. Inc., New York (1976).

H. Hajiabolhassan and M.L. Mehrabadi, On clique polynomials, Australas. J. Combin. 18 (1998), 313–316.

R.E. Tarjan, Decomposition by clique separators, Discrete Math. 55 (1985), 221–232.

M. Aigner, Turan’s graph theorem, Amer. Math. Monthly 6 (1995), 808–816.


  • There are currently no refbacks.

ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats