Distinguishing graphs by their left and right homomorphism profiles

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F11%3A10104595" target="_blank" >RIV/00216208:11320/11:10104595 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1016/j.ejc.2011.03.012" target="_blank" >http://dx.doi.org/10.1016/j.ejc.2011.03.012</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.ejc.2011.03.012" target="_blank" >10.1016/j.ejc.2011.03.012</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Distinguishing graphs by their left and right homomorphism profiles

Popis výsledku v původním jazyce

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. We establish for which edge-weighted graphs H homomorphism functions from multigraphs G to H are specializations of the Tutte polynomial of G, in particular answering a question of Freedman, Lovasz 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 polynomial'' 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.

Název v anglickém jazyce

Distinguishing graphs by their left and right homomorphism profiles

Popis výsledku anglicky

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. We establish for which edge-weighted graphs H homomorphism functions from multigraphs G to H are specializations of the Tutte polynomial of G, in particular answering a question of Freedman, Lovasz 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 polynomial'' 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.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

<a href="/cs/project/1M0545" target="_blank" >1M0545: Institut Teoretické Informatiky</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2011

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

European Journal of Combinatorics

ISSN

0195-6698

e-ISSN

—

Svazek periodika

32

Číslo periodika v rámci svazku

7

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

29

Strana od-do

1025-1053

Kód UT WoS článku

000294580100007

EID výsledku v databázi Scopus

—