Roberson's weak conjecture for bounded Hadwiger number

From papers

For a graph GG, its Hadwiger number is the largest integer tt such that GG contains the complete graph KtK_t as a minor. Two graphs are homomorphism indistinguishable over a graph class if they admit the same number of homomorphisms from every graph in that class. Roberson's weak conjecture. For every k0k \geq 0, there exist non-isomorphic graphs GG and HH that are homomorphism indistinguishable over all graphs of Hadwiger number k\leq k. This is a concrete form of the question whether sparse graph classes can distinguish all non-isomorphic graphs. The paper proves the conjecture for vortex-free graph classes, while the general minor-excluded case remains unresolved.

Progress summary

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

Sources & referencesView supporting material

Primary source

Daniel Neuen and Tim Seppelt, “Distinguishing Graphs by Counting Homomorphisms from Sparse Graphs”, arXiv:2601.18602 (2026).

Solutions 0

No solutions have been posted yet.