Minimum orders of clique oddomorphism counterexamples

arXiv:2610.33283 · math.CO · Submitted 2026-10-23 · Read on arXiv

math.CO

Submitted: 2026-10-23

Updated: 2026-11-08

Comments: 78 pages, main article and technical companion combined; includes computational provenance and verifier source. Revised introduction and references; added original-odd-set-rooted K4 theorem and all-order small-fibre K6-to-K5 theorem, implying the seventeen-vertex bound

License: http://creativecommons.org/licenses/by/4.0/

The gist: 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…

Terminology

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 at least8 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. We also prove that every witness to K 4, of arbitrary order, has a K 4 minor with every branch meeting its original odd set. The roots need not be prescribed or have distinct colours. In six colours, we prove that a fibre of size at most two forces a K 5 minor rooted in the original odd set, with no bound on the other fibres. In particular every six-colour witness on at most seventeen vertices has such a model. 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 qualitative clique-target existence problem has been solved in recent work; our results concern exact source-order bounds and control of the original odd set.

Sources

Related papers