# zbMATH — the first resource for mathematics

The $$m$$-clique polynomial and its application to chromatic polynomials. (English) Zbl 0751.05038
Graph theory, combinatorics, algorithms, and applications, Proc. 2nd Int. Conf., San Francisco/CA (USA) 1989, 331-341 (1991).
[For the entire collection see Zbl 0734.00014.]
Let $$F_ m=\{K_ 1,K_ 2,\ldots,K_ m\}$$ be a finite family of complete graphs. In this paper the same weight $$w_ k$$ is assigned to all cliques with $$k$$ nodes and with each $$m$$-clique cover $$C$$ of $$G$$ (a spanning subgraph of $$G$$ in which every component belongs to $$F_ m$$) is associated the weight $$w(C)=\prod_ \alpha w_ \alpha$$, where the product is taken over all components of $$C$$. The $$m$$-clique polynomial of $$G$$ is $$\sum w(C)=\sum\prod_ \alpha w_ \alpha$$, where the summation is over all $$m$$-clique covers of $$G$$. This polynomial belongs to the family of $$F$$-polynomials defined by E. J. Farrell [J. Comb. Theory, Ser. B 26, 111-122 (1979; Zbl 0328.05006)]; the 2-clique polynomials are just the matching polynomials.
Connections between simple $$m$$-clique polynomials and chromatic polynomials are established and explicit chromatic polynomials for various classes of graphs are deduced on this way. The exact simple $$m$$- clique polynomials for several classes of graphs are derived and some previous results of E. J. Farrell, B. Loerinc, and E. J. Farrell and E. G. Whitehead jun. are rediscovered.

##### MSC:
 05C15 Coloring of graphs and hypergraphs 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)