The Universal Edge Elimination Polynomial and the Dichromatic Polynomial

The dichromatic polynomial Z(G;q,v) can be characterized as the most general C-invariant, i.e., a graph polynomial satisfying a linear recurrence with respect to edge deletion and edge contraction. Similarly, the universal edge elimination polynomial ξ(G;x,y,z) introduced in [Ilya Averbouch, Benny Godlin, and Johann A. Makowsky. An extension of the bivariate chromatic polynomial. Eur. J. Comb, 31(1):1-17, 2010] can be characterized as the most general EE-invariant, i.e., a graph polynomial satisfying a linear recurrence with respect to edge deletion, edge contraction and edge extraction. In this paper we examine substitution instances of ξ(G;x,y,z) and show that among these the dichromatic polynomial Z(G;q,v) plays a distinctive rôle.