Artículo
Distinguishing graphs by their left and right homomorphism profiles
Autor/es | Garijo Royo, Delia
Goodall, Andrew Nešetřil, Jaroslav |
Departamento | Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII) |
Fecha de publicación | 2011 |
Fecha de depósito | 2020-03-11 |
Publicado en |
|
Resumen | 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. |
Agencias financiadoras | Ministerio de Educación y Ciencia (MEC). España Junta de Andalucía |
Identificador del proyecto | MTM2008-05866-C03-01
FQM- 0164 P06-FQM-01649 |
Cita | 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. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
Distinguishing graphs.pdf | 621.2Kb | [PDF] | Ver/ | |