TOPICS
Search

Weak Roberson Conjecture


The weak Roberson conjecture states that any class F of finite simple graphs which excludes some finite simple graph and is closed under graph minors and disjoint union fails to distinguish some pair of nonisomorphic graphs by graph homomorphism counts (Roberson 2026). More precisely, there should exist nonisomorphic graphs X,Y for which

 hom(F,X)=hom(F,Y) for every F in F,

where hom(F,G) counts graph homomorphisms from F to G.

The conjecture remains open. The disproof of the strong Roberson conjecture does not refute this weaker statement (Kristjánsson 2026).


See also

Graph Homomorphism, Graph Minor, Strong Roberson Conjecture

Explore with Wolfram|Alpha

References

Kristjánsson, A. Á. "Counterexamples to the Strong Roberson Conjecture." 2 Oct 2026. https://arxiv.org/abs/2610.03550.Roberson, D. E. "Oddomorphisms and Homomorphism Indistinguishability over Graphs of Bounded Degree." J. Combin. Th. Ser. B 181, 1-61, 2026.

Cite this as:

Weisstein, Eric W. "Weak Roberson Conjecture." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/WeakRobersonConjecture.html

Subject classifications