Strong Roberson Conjecture on homomorphism distinguishing closed graph classes
Strong Roberson Conjecture on homomorphism distinguishing closed graph classes
Let be a class of graphs. It is homomorphism distinguishing closed if it is maximal among the classes defining its homomorphism indistinguishability relation. A graph class is minor closed if it contains every minor of each of its graphs, and it is closed under disjoint unions if the disjoint union of any two members belongs to the class. Strong Roberson Conjecture. Every class of graphs that is minor closed and closed under disjoint unions is homomorphism distinguishing closed. Homomorphism indistinguishability relations connect graph homomorphism counts with structural and logical equivalence; the conjecture is known for several important classes, including planar graphs and classes of bounded treewidth or treedepth, but remains open in general.
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
Arnar Á. Kristjánsson, “Oddomorphisms, Split-Off Minors, and the Strong Roberson Conjecture”, arXiv:2607.03405 (2026).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.