Oddomorphisms, Split-Off Minors, and the Strong Roberson Conjecture

2026/07/03 by Arnar Á. Kristjánsson · 1 voice
Computer Science · Mathematics · #cs.DM #cs.LO #math.CO

paper · pdf

Abstract

We show that the existence of an oddomorphism from a graph F to a graph G does not imply that G is a minor of F. This answers a question posed by Roberson (2022) and shows that the CFI graphs cannot be used to prove the Strong Roberson Conjecture. Additionally, we introduce the concept of a split-off minor and show that the existence of an oddomorphism from F to G implies that G is a split-off minor of F. Consequently, every class that is closed under taking split-off minors and disjoint unions is homomorphism distinguishing closed. The split-off minor relation is the first minor-like structural relation shown to have this property, marking a meaningful advancement in our understanding of the interaction between structural graph containment and homomorphism indistinguishability relations.

Citations

• Homomorphism Indistinguishability and Game Comonads for Restricted Conjunction and Requantification
• Compressing CFI Graphs and Lower Bounds for the Weisfeiler-Leman Refinements
• Going Deep and Going Wide: Counting Logic and Homomorphism Indistinguishability over Graphs of Bounded Treedepth and Treewidth
• Count on CFI graphs for #P-hardness
• Homomorphism-Distinguishing Closedness for Graphs of Bounded Tree-Width
• Oddomorphisms and homomorphism indistinguishability over graphs of bounded degree
• The Weisfeiler-Leman Algorithm and Recognition of Graph Properties
• Counting Bounded Tree Depth Homomorphisms
• Quantum isomorphism is equivalent to equality of homomorphism counts from planar graphs
• Forcing clique immersions through chromatic number
• Rank logic is dead, long live rank logic!
• On recognizing graphs by numbers of homomorphisms
• Graph Minors. XX. Wagner's conjecture
• An optimal lower bound on the number of variables for graph identification
• Graph minors. V. Excluding a planar graph

Discussions

• Arnar \'A. Kristj\'ansson: Oddomorphisms, Split-Off Minors, and the Strong Roberson Conjecture https://arxiv.org/abs/2607.03405 https://arxiv.org/pdf/2607.03405 https://arxiv.org/html/2607.03405 [bsky, 0 points, 0 comments]

Related

• On the excluded minor structure theorem for graphs of large treewidth
• Forbidden Minors For 3-Connected Graphs With No Non-Splitting 5-Configurations
• Quickly excluding a non-planar graph
• Forbidden minors: Finding the finite few
• Disproof of the Odd Hadwiger Conjecture