Roberson's weak conjecture for bounded Hadwiger number
Roberson's weak conjecture for bounded Hadwiger number
For a graph , its Hadwiger number is the largest integer such that contains the complete graph 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 , there exist non-isomorphic graphs and that are homomorphism indistinguishable over all graphs of Hadwiger number . 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
Sign in to submit a solution.
No solutions have been posted yet.