Connections between the matching and chromatic polynomials (Q1205617)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Connections between the matching and chromatic polynomials
scientific article

    Statements

    Connections between the matching and chromatic polynomials (English)
    0 references
    0 references
    1 April 1993
    0 references
    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.
    0 references
    matching polynomial
    0 references
    matching
    0 references
    chromatic polynomial
    0 references

    Identifiers