3 papers
math.CO2026
Counterexamples to the Strong Roberson Conjecture
Arnar Á. Kristjánsson
We refute the Strong Roberson Conjecture, which asserts that adding any graph outside a class closed under minors and disjoint unions strictly increases the distinguishing power of…
cs.DM2026
Oddomorphisms, Split-Off Minors, and the Strong Roberson Conjecture
Arnar Á. Kristjánsson
We show that the existence of an oddomorphism from a graph to a graph does not imply that is a minor of . This answers a question posed by Roberson (2022) and shows…
cs.LO2025
Adaptive Query Algorithms for Relational Structures Based on Homomorphism Counts
Balder ten Cate, Phokion G. Kolaitis, Arnar Á. Kristjánsson
A query algorithm based on homomorphism counts is a procedure to decide membership for a class of finite relational structures using only homomorphism count queries. A left query a…