Minimum orders of clique oddomorphism counterexamples
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
- Kempe Chains and Rooted Minors
- Distinguishing Graphs by Counting Homomorphisms from Sparse Graphs
- Subdivisions of maximal 3-degenerate graphs of order $d+1$ in graphs of minimum degree $d$
- Homomorphism counting for immersion-closed classes is not isomorphism
- Counterexamples to the Strong Roberson Conjecture
- Oddomorphisms, Split-Off Minors, and the Strong Roberson Conjecture
- Oddomorphisms and homomorphism indistinguishability over graphs of bounded degree
Related papers
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality