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.

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