Lovász's planar graph homomorphism isomorphism question
Lovász's planar graph homomorphism isomorphism question
Let and be two simple graphs, possibly with loops. For every planar multigraph , possibly with multiple edges but no loops, consider the homomorphism counts and .
Lovász's planar homomorphism question. If
for every such planar multigraph , does it follow that and are isomorphic?
The unrestricted analogue is a theorem of Lovász, but the corresponding statement when the input graphs are restricted to planar graphs was not known in the source. This question concerns whether planar homomorphism counts determine the target graph up to isomorphism.
Sources & referencesView supporting material
Primary source
Jin-Yi Cai and Artem Govorov, “On a Theorem of Lovász that (, H) Determines the Isomorphism Type of H”, arXiv:1909.03693 (2021).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.