Lovász's planar graph homomorphism isomorphism question

About 7 years old · traced to

Let HH and H′H' be two simple graphs, possibly with loops. For every planar multigraph GG, possibly with multiple edges but no loops, consider the homomorphism counts hom⁡(G,H)\hom(G,H) and hom⁡(G,H′)\hom(G,H').

Lovász's planar homomorphism question. If

hom⁡(G,H)=hom⁡(G,H′)\hom(G,H)=\hom(G,H')

for every such planar multigraph GG, does it follow that HH and H′H' 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.

References

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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.