Roberson's homomorphism-counting conjecture for proper minor-closed classes

About 3 years old · traced to

Let M\mathcal{M} be a graph class that is proper, minor-closed, and union-closed. For graphs GG and HH, write G=MHG =_{\mathcal{M}} H when hom⁡(K,G)=hom⁡(K,H)\hom(K,G)=\hom(K,H) for every K∈MK\in\mathcal{M}. Roberson's conjecture. If M\mathcal{M} is a proper, minor-closed, and union-closed graph class, then there are non-isomorphic graphs GG and HH such that

G=MH.G =_{\mathcal{M}} H.

This conjecture says that homomorphism counts from any such proper minor-closed class do not characterize graphs up to isomorphism. The source attributes it to Roberson; its resolution is not specified here.

References

Primary source

Andrea Jiménez, Benjamin Moore, Daniel A. Quiroz and Youngho Yoo, “Homomorphism counting for immersion-closed classes is not isomorphism”, arXiv:2602.08738 (2026).

Additional references

3 papers in this index state this conjecture (2023–2026). The statement above is taken from the most recent of them; the others are arXiv:2601.18602, arXiv:2304.07011.

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.