# zbMATH — the first resource for mathematics

Connections between the matching and chromatic polynomials. (English) Zbl 0799.05053
A $$k$$-matching in a graph $$G$$ is a set of $$k$$ vertex-disjoint edges, i.e., a matching of size $$k$$. Let $$p(G,k)$$ denote the number of $$k$$- matchings in $$G$$. R. W. Frucht and R. E. Giudici have observed in [“A note on the matching numbers of triangle-free graphs”, J. Graph Theory 9, No. 4, 455-458 (1985; Zbl 0664.05046)] that if $$G$$ and $$H$$ are triangle-free and $$p(G,k)= p(H,k)$$ for all $$k$$ then their complements have the same chromatic polynomial—if the complement of $$G$$ is triangle-free there is a natural correspondence between $$k$$-matchings in the complement and $$k$$-colourings of $$G$$.
This paper discusses this connection in somewhat more detail, and also considers the relation between the number of $$k$$-matchings in $$G$$ and its complement. If $$G$$ is a subgraph of $$H$$, let $$G_ H$$ denote the graph formed by the edges in $$H$$ but not $$G$$. The authors derive a formula for $$p(G_ H,k)$$, that they use to provide new proofs of a number of known results.

##### MSC:
 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) 05A99 Enumerative combinatorics 05C99 Graph theory
##### Keywords:
matching polynomial; matching; chromatic polynomial
Full Text: