On recognizing graphs by numbers of homomorphisms

DOI10.1002/jgt.20461zbMath1207.05128MaRDI QIDQ3057061

Zdeněk Dvořák

Publication date: 24 November 2010

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/jgt.20461

zbMATH Keywords

graph homomorphisms; graph reconstruction; number of homomorphisms

Mathematics Subject Classification ID

05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)

Related Items

The Power of the Weisfeiler--Leman Algorithm to Decompose Graphs, On the Weisfeiler-Leman dimension of fractional packing, On Weisfeiler-Leman invariance: subgraph counts and related graph properties, Perfect matchings, rank of connection tensors and graph homomorphisms, Approximating fractionally isomorphic graphons, Weisfeiler-Leman indistinguishability of graphons, Polyadic sets and homomorphism counting, Fractional isomorphism of graphons, Discrete density comonads and graph parameters, Local WL invariance and hidden shades of regularity

Cites Work

• Unnamed Item
• The complexity of counting homomorphisms seen from the other side
• 6-transitive graphs
• An optimal lower bound on the number of variables for graph identification
• Linear time low tree-width partitions and algorithmic consequences
• Contractors and connectors of graph algebras
• Distinguishing graphs by the number of homomorphisms
• Operations with structures