An extension of the bivariate chromatic polynomial

作者：Averbouch Ilia^*; Godlin Benny; Makowsky J A

来源：European Journal of Combinatorics, 2010, 31(1): 1-17.

DOI：10.1016/j.ejc.2009.05.006

K. Dohmen, A. Ponitz and P. Tittmann [K. Dohmen, A. Ponitz, 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) 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 I 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) has a recursive definition with respect to three kinds of edge eliminations: edge deletion, edge contraction, and edge extraction, i.e. deletion of ail 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. Murry (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 xi(G, x, y, z). We show that the new polynomial simultaneously generalizes, P(G, x, y), as well as the Tutte polynomial and the marching polynomial, We also give ail explicit definition of xi(G, X, Y, Z) using a Subset expansion formula. We also show that xi(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. Bollobas and O. Riordan [B. Bollobas, O. Riordan, A Tutte polynomial for coloured graphs, Combinatorics, Probability and Computing 8 (1999). 45-94]. The edge-labeled polynomial xi(lab)(G, x, y, z, (t) over bar) 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).

• 出版日期2010-1