Minor-separating graph-pair conjecture

Let GG be a connected graph, and let HH and HH' 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 HH' 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 HFGHH\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.

Sources & referencesView supporting material

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.