More connections between the matching polynomial and the chromatic polynomial

Abstract

The connection between the matching polynomial and the chromatic polynomial for triangle-free graphs was revealed in the work of Farrell and Whitehead. We extend this result to all graph by mirroring the corresponding result of Godsil and Gutman for the acyclic polynomial and the characteristic polynomial. We also reintroduce the clique polynomial of Farrell as an evaluation of the U-polynomial of Noble and Welsh, which also happens to contain the matching and chromatic polynomials.

Keywords

• matching polynomial
• chromatic polynomial
• f-polynomial
• u-polynomial