Connections between the matching and chromatic polynomials (Q1205617)

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\). \textit{R. W. Frucht} and \textit{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.