Back to Search
Start Over
Graph homomorphisms, the Tutte polynomial and 'q-state Potts uniqueness'
- Source :
- idUS. Depósito de Investigación de la Universidad de Sevilla, instname
- Publication Year :
- 2009
- Publisher :
- Elsevier BV, 2009.
-
Abstract
- We establish for which weighted graphs H homomorphism functions from multigraphs G to H are specializations of the Tutte polynomial of G, answering a question of Freedman, Lov´asz and Schrijver. We introduce a new property of graphs called “q-state Potts uniqueness” and relate it to chromatic and Tutte uniqueness, and also to “chromatic–flow uniqueness”, recently studied by Duan, Wu and Yu. Ministerio de Educación y Ciencia MTM2005-08441-C02-01
- Subjects :
- Flow polynomial
Discrete mathematics
Mathematics::Combinatorics
q-state Potts partition function
Applied Mathematics
Nowhere-zero flow
Computer Science::Computational Complexity
Chromatic polynomial
Graph homomorphism
Tutte theorem
Combinatorics
Tutte polynomial
Computer Science::Discrete Mathematics
Discrete Mathematics and Combinatorics
Tutte 12-cage
Graph coloring
Tutte matrix
Homomorphism profile
Polyhedral graph
Mathematics
Subjects
Details
- ISSN :
- 15710653 and 20050844
- Volume :
- 34
- Database :
- OpenAIRE
- Journal :
- Electronic Notes in Discrete Mathematics
- Accession number :
- edsair.doi.dedup.....e6b9b2543b10d9a324c4e3a6f63c53af
- Full Text :
- https://doi.org/10.1016/j.endm.2009.07.038