TOPICS
Search

Strong Roberson Conjecture

The strong Roberson conjecture states that a class F of finite simple graphs closed under graph minors and disjoint union is homomorphism distinguishing closed (Roberson 2026). Explicitly, for every graph H not in F, there should exist graphs X,Y such that

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

but hom(H,X)!=hom(H,Y), where hom(G,H) counts graph homomorphisms from G to H.

Kristjánsson (2026) disproved the conjecture. For the circulant graph H=Ci_(101)(1,5), counts from all graphs excluding H as a graph minor determine the count from H itself. The corresponding class is closed under graph minors and disjoint union, but adding H does not increase its distinguishing power. Kristjánsson (2026) reports substantial AI assistance in developing the results, and accepts responsibility for correctness. The weak Roberson conjecture remains open.

See also

Graph Homomorphism, Graph Minor, Weak 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. "Strong Roberson Conjecture." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/StrongRobersonConjecture.html

Subject classifications