Connections between the matching and chromatic polynomials
type: Item
instance of: scholarly article
title: Connections between the matching and chromatic polynomials
zbMATH Open document ID: 0799.05053
DOI: 10.1155/S016117129200098X
author: E. J. Farrell
author: Earl Glen jun. Whitehead
published in: International Journal of Mathematics and Mathematical Sciences
publication date: 1993-04-01T00:00:00Z
full work available at URL: https://eudml.org/doc/47005
review text: 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.
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05A99
Mathematics Subject Classification ID: 05C99
zbMATH DE Number: 147583
zbMATH Keywords: matching polynomial
zbMATH Keywords: matching
zbMATH Keywords: chromatic polynomial
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 147583