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.

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05A99 Enumerative combinatorics
05C99 Graph theory
Full Text: DOI EuDML