Journal article icon

Journal article

On counting generalized colorings

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 po...

Expand abstract

Actions


Access Document


Publisher copy:
10.1007/978-3-540-87531-425

Authors


Journal:
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume:
5213 LNCS
Pages:
339-353
Publication date:
2008-01-01
DOI:
EISSN:
1611-3349
ISSN:
0302-9743
URN:
uuid:b0144f08-065f-4f35-a8bc-53de49d8fcd7
Source identifiers:
148861
Local pid:
pubs:148861
Language:
English

Terms of use


Metrics


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP