Article
Distinguishing graphs by their left and right homomorphism profiles
Author/s | Garijo Royo, Delia
Goodall, Andrew Nešetřil, Jaroslav |
Department | Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII) |
Publication Date | 2011 |
Deposit Date | 2020-03-11 |
Published in |
|
Abstract | We introduce a new property of graphs called ‘q-state Potts unique-ness’ and relate it to chromatic and Tutte
uniqueness, and also to ‘chromatic–flow uniqueness’, recently studied by Duan, Wu and Yu.
We establish for ... We introduce a new property of graphs called ‘q-state Potts unique-ness’ and relate it to chromatic and Tutte uniqueness, and also to ‘chromatic–flow uniqueness’, recently studied by Duan, Wu and Yu. We establish for which edge-weighted graphs H homomor-phism functions from multigraphs G to H are specializations of the Tutte polynomial of G, in particular answering a question of Freed-man, Lovász and Schrijver. We also determine for which edge-weighted graphs H homomorphism functions from multigraphs G to H are specializations of the ‘edge elimination polynomial’ of Averbouch, Godlin and Makowsky and the ‘induced subgraph poly-nomial’ of Tittmann, Averbouch and Makowsky. Unifying the study of these and related problems is the notion of the left and right homomorphism profiles of a graph. |
Funding agencies | Ministerio de Educación y Ciencia (MEC). España Junta de Andalucía |
Project ID. | MTM2008-05866-C03-01
FQM- 0164 P06-FQM-01649 |
Citation | Garijo Royo, D., Goodall, A. y Nešetřil, J. (2011). Distinguishing graphs by their left and right homomorphism profiles. European Journal of Combinatorics, 32 (7), 1025-1053. |
Files | Size | Format | View | Description |
---|---|---|---|---|
Distinguishing graphs.pdf | 621.2Kb | [PDF] | View/ | |