Minor-separating graph-pair conjecture

At least 3 years old · documented by

Let GG be a connected graph, and let HH and H′H' be graphs. Write hom⁡(F,H)\hom(F,H) for the number of homomorphisms from FF to HH. Minor-separating graph-pair conjecture. For every connected graph GG, there exist graphs HH and H′H' such that

hom⁡(G,H)≠hom⁡(G,H′)\hom(G,H)\ne\hom(G,H')

and

hom⁡(F,H)≠hom⁡(F,H′) ⟹ F contains G as a minor.\hom(F,H)\ne\hom(F,H')\ \Longrightarrow\ F\text{ contains }G\text{ as a minor}.

Equivalently, if FG\mathcal{F}_G is the family of graphs not containing GG as a minor, then H≅FGH′H\cong_{\mathcal{F}_G}H' but the homomorphism counts from GG differ. The paper describes this as one of four equivalent open conjectures and regards it as the most approachable.

References

Primary source

David E. Roberson, “Oddomorphisms and homomorphism indistinguishability over graphs of bounded degree”, arXiv:2206.10321 (2022).

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.