An extension of the bivariate chromatic polynomial

K. Dohmen, A. Pönitz and P. Tittmann [K. Dohmen, A. Pönitz, P. Tittmann, A new two-variable generalization of the chromatic polynomial, Discrete Mathematics and Theoretical Computer Science 6 (2003), 69–90], introduced a bivariate generalization of the chromatic polynomial P(G,x,y)P(G,x,y) which subsumes also the independent set polynomial of I. Gutman and F. Harary [I. Gutman, F. Harary, Generalizations of the matching polynomial, Utilitas Mathematicae 24 (1983), 97–106] and the vertex-cover polynomial of F.M. Dong, M.D. Hendy, K.T. Teo and C.H.C. Little [F.M. Dong, M.D. Hendy, K.L. Teo, and C.H.C. Little, The vertex-cover polynomial of a graph, Discrete Mathematics 250 (2002), 71–78]. We first show that P(G,x,y)P(G,x,y) has a recursive definition with respect to three kinds of edge eliminations: edge deletion, edge contraction, and edge extraction, i.e. deletion of an edge together with its endpoints. Like in the case of deletion and contraction only [J.G. Oxley and D.J.A. Welsh, The Tutte polynomial and percolation, in: J.A. Bundy, U.S.R. Murty (Eds.), Graph Theory and Related Topics, Academic Press, London, 1979, pp. 329–339] it turns out that there is a most general, or as they call it, a universal polynomial satisfying such recurrence relations with respect to the three kinds of edge eliminations, which we call ξ(G,x,y,z)ξ(G,x,y,z). We show that the new polynomial simultaneously generalizes, P(G,x,y)P(G,x,y), as well as the Tutte polynomial and the matching polynomial, We also give an explicit definition of ξ(G,x,y,z)ξ(G,x,y,z) using a subset expansion formula. We also show that ξ(G,x,y,z)ξ(G,x,y,z) can be viewed as a partition function, using counting of weighted graph homomorphisms. Furthermore, we expand this result to edge-labeled graphs as was done for the Tutte polynomial by T. Zaslavsky [T. Zaslavsky, Strong Tutte functions of matroids and graphs, Trans. Amer. Math. Soc. 334 (1992), 317–347] and by B. Bollobás and O. Riordan [B. Bollobás, O. Riordan, A Tutte polynomial for coloured graphs, Combinatorics, Probability and Computing 8 (1999), 45–94]. The edge-labeled polynomial ξlab(G,x,y,z,t̄) also generalizes the chain polynomial of R.C. Read and E.G. Whitehead Jr. [R.C. Read, E.G. Whitehead Jr., Chromatic polynomials of homeomorphism classes of graphs, Discrete Mathematics 204 (1999), 337–356]. Finally, we discuss the complexity of computing ξ(G,x,y,z)ξ(G,x,y,z).