Minimum orders of clique oddomorphism counterexamples

Source abstract

An oddomorphism to $K_n$ is a proper colouring with $n$ colours in which every vertex is designated odd or even, every vertex has in each other colour class a number of neighbours of its own parity, and every colour class contains an odd number of odd vertices. We prove that an oddomorphism witness to $K_n$ on at most $n+6$ vertices contains a $K_n$ minor with every branch meeting the witness's specified odd set. The conclusion holds inside any graph containing the witness and therefore applies to weak oddomorphisms. The bound is sharp: for every $n\ge8$ the minimum order of a graph admitting a weak oddomorphism to $K_n$ but having no $K_n$ minor is exactly $n+7$. The extremal example is a fifteen-vertex graph with an oddomorphism to $K_8$, obtained from the doubled theta graph of Kriesell and Mohr by adding one vertex adjacent to the seven roots; we give a structural proof that it has no $K_8$ minor, including their counting argument for the rooted case. A separate technical companion records further results on related root-apex graphs, an attachment theorem and a bounded nine-colour statement, together with their computational provenance; none of it is used here. The results do not resolve the unrestricted clique-target problem.