scientific article; zbMATH DE number 19199

MaRDI QIDQ3976629zbMATH OpenFDO

Authors Zhi-Yi Guo, Nian Zu Li

Publication date 26 June 1992

zbMATH Keywords

\(m\)-clique cover\(m\)-clique polynomialchromatic polynomialcliquematching polynomial

Mathematics Subject Classification ID

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

Review text

[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 \textit{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.

Recommendations

• More connections between the matching polynomial and the chromatic polynomial
• On a class of polynomials associated with the cliques in a graph and its applications
• scientific article; zbMATH DE number 1229629
• scientific article; zbMATH DE number 2094520
• Estimates of coefficients of chromatic polynomials and numbers of cliques of (c,n,m)-graphs

Cited in

(9)

• The search for chromatically unique graphs. II
• The Clar covering polynomial of hexagonal systems with an application to chromatic polynomials
• A bibliography on chromatic polynomials
• More connections between the matching polynomial and the chromatic polynomial
• On a class of polynomials associated with the cliques in a graph and its applications
• scientific article; zbMATH DE number 2076811 (Why is no real title available?)
• Estimates of coefficients of chromatic polynomials and numbers of cliques of (c,n,m)-graphs
• scientific article; zbMATH DE number 2094520 (Why is no real title available?)
• scientific article; zbMATH DE number 798649 (Why is no real title available?)

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3976629)