On counting generalized colorings

Author: 

Kotek, T
Makowsky, J
Zilber, B

Publication Date: 

25 December 2008

Journal: 

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Last Updated: 

2021-08-24T11:25:32.853+01:00

Volume: 

5213 LNCS

DOI: 

10.1007/978-3-540-87531-425

page: 

339-353

abstract: 

It is well known that the number of proper k-colorings of a graph is a polynomial in k. We investigate in this talk under what conditions a numeric graph invariant which is parametrized with parameters k 1, ..., k m is a polynomial in these parameters. We give a sufficient conditions for this to happen which is general enough to encompass all the graph polynomials which are definable in Second Order Logic. This not only covers the various generalizations of the Tutte polynomials, Interlace polynomials, Matching polynomials, but allows us to identify new graph polynomials related to combinatorial problems discussed in the literature. © 2008 Springer-Verlag Berlin Heidelberg.

Symplectic id: 

148861

Submitted to ORA: 

Not Submitted

Publication Type: 

Journal Article

ISBN-13: 

9783540875307

ISBN-10: 

3540875301