Author
Kotek, T
Makowsky, J
Zilber, B
Journal title
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
DOI
10.1007/978-3-540-87531-425
Volume
5213 LNCS
Last updated
2022-01-29T13:27:39.3+00:00
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
Favourite
Off
Publication type
Journal Article
ISBN-13
9783540875307
ISBN-10
3540875301
Publication date
25 Dec 2008
Please contact us for feedback and comments about this page. Created on 06 Jun 2011 - 04:58.