Clique polynomials and independent set polynomials of graphs (Q1322274)

Clique and independent set polynomials for graphs are defined and their basic properties are listed. The clique polynomial of a graph \(G\), denoted by \(C(G;x)\), is defined as a generating function for the sequence \([a_ k]\) of the numbers of \(k\)-cliques of \(G\). Similarly the independent set polynomial, denoted by \(I(G;x)\), is a generating function for the sequence \([b_ k]\) of the numbers of \(k\)-independent sets of \(G\). A special interest is given to subgraph expansions of \(C(G;x)\) and \(I(G;x)\), i.e. the relations between \(F(G- U;x)\) and \(F(G;x)\), where \(U\) is a subgraph of \(G\) and \(F\) one of the polynomials mentioned above. Some open problems concerning polynomials are formulated.