Clique Polynomials and a New Algebro-Geometric Proof of Turan's Graph Theorem
A clique polynomial of a finite simple graph G=(V,E) is a polynomial C(G,x) defined, as
C(G,x)=1+∑∅≠U⊆V(G):G[U] is a cliquex|U|,
where the sum runs over all induced subgraphs G[U] that are cliques (complete subgraphs) in G.
Hajiabolhasan and Mehrabadi proved that all roots of the clique polynomial of a triangle - free graph are real. Consequently, they presented a new elementary and algebraic proof of Mantel's theorem for triangle - free graphs. Moreover, Teimoori showed that the clique polynomial of the class of K4 - free connected planar chordal graphs has only real roots.
Here, while reviewing the algebraic properties of the clique polynomials, we give a generalization of the previous results by presenting a new algebro - geometric proof of Turan's graph theorem using some ideas from cylindrical constructions on finite graphs. We conclude our talk, by proposing some open questions regarding clique polynomials and Turan-type results.