betaFeedback

WorksMathematics

Minimum orders of clique oddomorphism counterexamples

Abstract

An oddomorphism to KnK_n is a proper colouring with nn 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 KnK_n on at most n+6n+6 vertices contains a KnK_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≥8n\ge8 the minimum order of a graph admitting a weak oddomorphism to KnK_n but having no KnK_n minor is exactly n+7n+7. The extremal example is a fifteen-vertex graph with an oddomorphism to K8K_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 K8K_8 minor, including their counting argument for the rooted case. We also prove that every witness to K4K_4, of arbitrary order, has a K4K_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 K5K_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.

Main article

Results and their scope

The relation between parity-constrained graph homomorphisms and clique minors has two different quantitative aspects. One asks whether a sufficiently large complete target forces a prescribed clique minor without restricting the source. Another fixes the target and asks how small a counterexample can be. This paper studies the latter question through the excess ∣V(W)∣−n|V(W)|-n of a witness to KnK_n. We also prove an unrestricted rooted result for the target K4K_4 and an all-order rooted-five result for six-colour witnesses with a fibre of size at most two.

Roberson introduced oddomorphisms and their weak variant and related them to homomorphism counts of parity constructions [14]. The general implication from an oddomorphism to containment of its target as a minor is false: Kristjánsson gives counterexamples, including complete targets [11]. His examples for the target KnK_n come from random 3-lifts of KnK_n, using a result of Drier and Linial on minors in random lifts [3]; they have 3n3n vertices and exist for all sufficiently large nn [11 Section 3.2]. We determine the least order of such a counterexample exactly: it is n+7n+7 for every n≥8n \ge8.

In subsequent work, Kristjánsson refuted the Strong Roberson Conjecture itself and its immersion analogue [10 Theorems 1 and 14]. Those counterexamples concern non-complete targets and do not determine the minimum order considered here.

Theorem 1.1 (Rooted excess six). Let n≥2n \ge2. Suppose a finite simple graph FF contains a subgraph WW with an oddomorphism to KnK_n and specified odd set PP. If ∣V(W)∣≤n+6|V(W)| \le n+6, then WW has a KnK_n minor with every branch set meeting PP. In particular, the same model exists in FF.

This formulation is slightly stronger than a host-order bound: vertices outside WW do not count. In particular, a graph of order at most n+6n+6 with a weak oddomorphism to KnK_n satisfies the conclusion. A branch is only required to contain a specified odd vertex; it is not required to contain an odd number of such vertices, remain within a fibre, or have a prescribed colour.

The word odd refers to the parity conditions of § 1.2: on the number of neighbours of a vertex in each other colour class, and on the number of odd vertices in each colour class. It is unrelated to odd minors, which occur in the odd-minor variant of Hadwiger’s conjecture. There a graph contains an odd KnK_n minor if it has nn vertex-disjoint trees, every two joined by an edge, whose vertices can be two-coloured so that the edges of the trees are bichromatic and the joining edges are monochromatic [5]. All minors in this paper are ordinary minors.

Theorem 1.2 (Sharpness). For n≥8n \ge8, let m(n)m(n) be the minimum order of a graph admitting a weak oddomorphism to KnK_n but having no KnK_n minor. Then m(n)=n+7m(n)=n+7. An extremal example can be chosen to admit an oddomorphism. In particular, m(8)=15m(8)=15.

The construction uses the theta-based two-vertex-fibre graph of Kriessell and Mohr [9 Section 3, pp. 8–9, immediately before Theorem 2]. Its rooted obstruction is theirs (their Theorem 2 states it as the failure of a rooted routing property); it already shows that a uniform rooted excess-seven theorem fails at n=7n=7, and we include their counting argument in Lemma 5.3. The assertion needed for Theorem 1.2 is stronger and different: adjoining a vertex adjacent to the seven designated roots produces no ordinary K8K_8 minor. The rooted obstruction excludes only the models in which the new vertex forms a singleton branch; an ordinary model may have a different singleton branch or put the new vertex into a larger branch. We exclude every model structurally in Proposition 5.4 using a spanning-model reduction, singleton saturation, and eight elementary cases.

Theorem 1.3 (Rooted four-colour witnesses). Every oddomorphism witness to K4K_4 with specified odd set PP contains a PP-rooted K4K_4 model, with no restriction on its order. Consequently, the same conclusion holds in any graph containing such a witness.

This is a set-rooted assertion: each of the four disjoint connected pairwise adjacent branches meets the original set PP. It does not prescribe four particular roots or require the roots to have distinct colours. The proof in Section 6 is independent of Theorem 1.1, uses no computation, and allows arbitrarily many odd vertices in a fibre.

Theorem 1.4 (A small fibre in six colours). Every oddomorphism witness to K6K_6 with specified odd set PP and a fibre of size at most two contains a PP-rooted K5K_5 model. Consequently, every specified K6K_6 witness on at most seventeen vertices has such a model. The same model lies in every graph containing the witness.

There is no bound on the other five fibre sizes in the first assertion. Thus a counterexample to original-set-rooted K5K_5 forcing from six colours, if one exists, has all six fibres of size at least three and order at least eighteen. No example at eighteen or sharpness assertion is claimed. A singleton fibre was already sufficient by Theorem 1.3 and Lemma 2.3; the substantive extension is to a double. The proof in Section 7 restores original roots through separator quotients, reduces a hypothetical counterexample with a double to a four-connected witness, and applies the classical rural-society theorem. It is independent of Theorem 1.1 and uses no computation.

Relation to previous work. Three ingredients come from Kriesell and Mohr [9]: the doubled graphs Z(B)Z(B); their routing theorem for graphs BB on at most six vertices [9 Theorem 6, Section 5, p. 12]; and the doubled theta graph with completed root pairs, together with its rooted obstruction. We use the routing theorem only when the core of a witness consists of at most six double fibres. It is a statement about the graphs Z(B)Z(B), not about arbitrary six-colour Kempe routing, and the companion gives direct proofs of these cases. Twin deletion and parity-preserving merging also occur in recent work [13, 7]; we make no priority claim for those general ideas. For the target K5K_5, Neuen and Seppelt prove that the class of K5K_5-minor-free graphs is closed under weak oddomorphisms [13, Theorem 5.22 in arXiv version 2]. Hence a weak oddomorphism to K5K_5 forces a K5K_5 minor whatever the order of the source, but this does not give the rooted conclusion of Theorem 1.1. Our contribution is the mixed-fibre excess-six theorem with its rooted conclusion, the exclusion of an ordinary K8K_8 minor in the fifteen-vertex graph (Proposition 5.4), and the resulting exact value of m(n)m(n). The additional contribution of Theorem 1.3 is the unrestricted conclusion for the full original odd set, including witnesses with several odd vertices in a fibre. A comparison with the primary sources cited here found no earlier statement of the threshold m(n)=n+7m(n)=n+7. That comparison was limited in scope and is not a certification of novelty.

For comparison with Theorem 1.3, Kriesell and Mohr prove a rooted K4K_4 theorem for a prescribed transversal of a four-colouring when each pair of transversal vertices is joined in the corresponding two-colour graph [9 Theorem 4]. If each fibre of an oddomorphism witness has exactly one odd vertex, handshaking in each two-colour component gives those paths, so that case was already covered. With several odd vertices in a fibre, the witness equations do not supply a compatible prescribed transversal. Our proof instead pairs all odd-degree endpoints in each two-colour graph and uses a cyclic parity identity. The cycle principle is recorded in Groenland, Nederlof and Koana [6 Lemma 4], and the crossing-linkage implication is due to Fabila-Monroy and Wood [4 Lemma 7]; these ingredients are not claimed as new. The comparison with these sources did not locate the general original-set-rooted statement, but it is not an exhaustive certification of novelty.

For Theorem 1.4, the new point is the interaction of witness parity, whole-colour deletion and original-root-preserving supports at three-separators, which makes the four-connected clean-root argument applicable to an arbitrary-order double. The three-terminal support criterion is classical: Fabila-Monroy and Wood [4 Lemma 1] attribute it to Wood and Linusson. The rural-society theorem is due to Robertson and Seymour [15]; we use the precise formulation in [8 Theorem 2.5]. Planarity preservation under weak oddomorphisms is Roberson’s [14 Lemma 8.2 in arXiv version 1]. These ingredients are not new, and the targeted comparison with these sources is not an exhaustive priority determination. The theorem is also distinct from the five-colour prescribed-transversal question of Kriesell and Mohr [9 Section 7]: it has six colours and a small fibre, and requires five branches to meet the odd set rather than assigning five specified roots to them.

Roberson’s Question 7 asks whether, for every tt, some complete target KNK_N forces a KtK_t minor under a weak oddomorphism [14]. Kristjánsson, Moore, Neuen, Roberson, Seppelt and Young answer this question affirmatively in their working paper A Proof of the Weak Roberson Conjecture [12 Theorem 1.3], posted on 14 October 2026. Thus the qualitative clique-target existence problem is solved by that result; it is no longer an open problem motivating the present paper. Their theorem gives a finite target threshold for each prescribed minor order without a source-order bound. It does not give the exact extremal source order m(n)=n+7m(n) = n + 7 proved here, nor does its stated conclusion require branches to meet a witness’s original odd set. The working-paper status of that source is retained in the citation; none of our proofs uses its theorem.

The unrestricted same-target questions for K6K_6 and K7K_7 are not settled here. For n=5n = 5 the closure theorem of Neuen and Seppelt mentioned above rules out every counterexample, and for n≤4n \le4 ordinary forcing is already known; Theorem 1.3 strengthens the four-colour conclusion to the original odd set. We do not prove that every weak oddomorphism to K7K_7 forces a K6K_6 minor, or that every weak oddomorphism to K9K_9 forces a K8K_8 minor.

Organisation. Section 2 sets up witnesses and a root-preserving normalization. Sections 3 and 4 prove Theorem 1.1: the excess-five bound and the seven fibre patterns of excess six, including mixed fibres of sizes up to five. Section 5 constructs the fifteen-vertex graph, proves that it has no K8K_8 minor and deduces Theorem 1.2. Section 6 proves Theorem 1.3 by a root-preserving separator reduction and a cyclic parity argument. Section 7 proves Theorem 1.4 and its consequences through a double-preserving reduction and a clean-root theorem.

The technical companion. A separate companion document, whose section and statement numbers continue those of this paper, contains material that is not needed for Theorems 1.1 and 1.2: three extremal families found within a specified thirty-one-member family of root-apex graphs; a criterion for an even vertex attached to eight double fibres to force a K8K_8 minor; a classification of when the apex of the three hard root-apex graphs can remain a singleton branch after one extra edge is added; and a bounded computer-assisted theorem for weak oddomorphism witnesses to K9K_9 of order at most nineteen. For each statement it says whether the evidence is structural, certificate-backed or inherited.

Parity witnesses and reductions

All graphs are finite and simple. A KtK_t model is a family of tt nonempty pairwise disjoint connected vertex sets with an edge between every pair. For a specified set PP, a model is PP-rooted if each branch meets PP.

Definition 2.1. An oddomorphism witness to a KnK_n consists of a graph WW, a partition V1,…,VnV_1,\ldots,V_n

into independent sets, and p:V(W)→{0,1}p: V(W) \to\{0,1\} satisfying

∣NW(v)∩Vj∣≡p(v)(mod2)(v∈Vi, j≠i),(1)|N_W(v) \cap V_j| \equiv p(v) \pmod{2} \qquad(v \in V_i,\ j \ne i), \tag*{(1)}
∑v∈Vip(v)≡1(mod2)(1≤i≤n).(2)\sum_{v \in V_i} p(v) \equiv1 \pmod{2} \qquad(1 \le i \le n). \tag*{(2)}

Its odd set is P=p−1(1)P = p^{-1}(1). The fibres are nonempty by (2). A vertex supports a fibre if it has a neighbour in that fibre.

The fibre map is an oddomorphism in the usual sense. In the standard definition, a weak oddomorphism from FF to KnK_n is a homomorphism on all of FF whose restriction to a possibly noninduced subgraph WW is an oddomorphism [14 Definition 3.9]. Our witness-containment assertions do not require extending the fibre map to the host. Every parity calculation concerns WW, not any extra host edges.

Lemma 2.2 (Root-preserving normalization). Every specified witness WW has a minor witness HH to the same target such that every even vertex supports at least two other fibres. There exist disjoint connected sets Cx⊆V(W)C_x \subseteq V(W) for x∈V(H)x \in V(H) such that

pH(x)=∣Cx∩P∣(mod2),xy∈E(H)⇒EW(Cx,Cy)≠∅.p_H(x) = |C_x \cap P| \pmod{2}, \qquad xy \in E(H) \Rightarrow E_W(C_x,C_y) \ne\varnothing.

Consequently any model in HH rooted in pH−1(1)p_H^{-1}(1) lifts to a PP-rooted model in WW.

Proof. Initially use singleton supports. Delete any isolated even vertex. If an even vertex vv of colour rr has neighbours only in colour ii, put S=NH(v)S = N_H(v). Its size is positive and even. Contract the star on {v}∪S\{v\} \cup S to a vertex ww of colour ii. For each outside vertex zz, retain wzwz precisely when ∣NH(z)∩S∣|N_H(z) \cap S| is odd, deleting any other resulting edge. Every retained edge is available after contraction. No outside vertex is adjacent to vv, and no outside vertex of colour ii is adjacent to SS, so the colouring stays proper. Set pH(w)=∑u∈SpH(u)(mod2)p_H(w) = \sum_{u \in S} p_H(u) \pmod{2}.

Each outside vertex has the same degree parity into the new colour-ii fibre. For j≠ij \ne i the parity at the new vertex is

dVj′(w)≡∑u∈SdVj(u)−1j=r∣S∣≡∑u∈SpH(u)=pH(w)(mod2).d_{V_j'}(w) \equiv\sum_{u \in S} d_{V_j}(u) - \mathbf{1}_{j=r}|S| \equiv\sum_{u \in S} p_H(u) = p_H(w) \pmod{2}.

The subtraction removes the star edges to vv and is even. The colour-ii charge is unchanged and colour rr loses only an even vertex, so both retain odd charge. Set Cw=Cv∪⋃u∈SCuC_w = C_v \cup\bigcup_{u \in S} C_u. This is connected, preserves the asserted parity, and remains disjoint from all other supports. Every retained edge has a witnessing original edge. Each step strictly decreases order, so the procedure terminates.

For a connected branch A⊆V(H)A \subseteq V(H), the union ⋃x∈ACx\bigcup_{x \in A} C_x is connected in WW. These unions preserve disjointness and crossings. If AA contains an odd xx, then ∣Cx∩P∣|C_x \cap P| is odd and hence positive. This proves the lift. □

A witness satisfying the support condition of Lemma 2.2 is called normalized. This is a reduction property, not an assumption about arbitrary restrictions to fewer fibres.

Lemma 2.3 (Restriction and attachment). Deleting whole fibres leaves a witness on the remaining fibres with the same restricted indicator. A singleton fibre {s}\{s\} has p(s)=1p(s)=1 and, for every v∈V(W)∖{s}v \in V(W) \setminus\{s\}, satisfies sv∈E(W)sv \in E(W) if and only if p(v)=1p(v)=1. If a connected set AA contains a whole fibre ViV_i, then AA is adjacent to every disjoint branch containing an odd vertex outside ViV_i.

Proof. Whole-fibre deletion changes none of the retained equations (1)–(2). The singleton assertion follows from (2) and, for v≠sv \ne s (necessarily in another fibre), from (1), because degrees into {s}\{s\} are zero or one. An odd vertex outside ViV_i has positive odd degree into ViV_i, proving the final assertion.

Thus a rooted clique model on the nonsingleton fibres extends by all singleton fibres. Removing singletons also preserves normalization, since an even vertex has no singleton neighbour. We refer to the restriction to nonsingleton fibres as the core. Whole-fibre restriction is a special case of [14 Lemma 5.2]; the support bookkeeping above is recorded to fix the original roots through contractions.

Lemma 2.4 (Double interfaces). In a double fibre write Di={oi,ei}D_i = \{o_i, e_i\} with p(oi)=1p(o_i) = 1 and $p(e_i) = 0. Between two doubles exactly two interfaces are possible: the edge oiojo_i o_j, or the three edges oiej,eiej,eiojo_i e_j, e_i e_j, e_i o_j.

Proof. Writing b=[eiej∈E]b = [e_i e_j \in E], the two even parity equations give [oiej]=[eioj]=b[o_i e_j] = [e_i o_j] = b, and the odd equation gives [oioj]=1−b[o_i o_j] = 1 - b. These exhaust all four entries.

The active graph BB has an edge ijij for the three-edge interface. For an all-double core, normalization is equivalent to δ(B)≥2\delta(B) \ge2.

The excess five bound

Theorem 3.1. A specified witness to KnK_n on at most n+5n + 5 vertices has a PP-rooted KnK_n model.

Proof. Normalize by Lemma 2.2 and remove singleton fibres by Lemma 2.3. The following cases construct the required rooted core model.

References

  1. [1]Tigran Arsenyan. Kempe chains and rooted minors. Bachelor’s thesis, Charles University, Faculty of Mathematics and Physics, 2025. Defended 5 September 2025; available in the Charles University repository since 15 April 2026. https://dspace.cuni.cz/handle/20.500.11956/202604.
  2. [2]Ajit A. Diwan. Subdivisions of maximal 3-degenerate graphs of order d + 1 in graphs of minimum degree d, 2020. https://arxiv.org/abs/2004.08528.
  3. [3]Yotam Drier and Nathan Linial. Minors in lifts of graphs. Random Structures & Algorithms, 29(2):208–225, 2006. https://doi.org/10.1002/rsa.20100.
  4. [4]Ruy Fabila-Monroy and David R. Wood. Rooted K₄-minors. The Electronic Journal of Combinatorics, 20(2):P64, 2013. https://doi.org/10.37236/3476.
  5. [5]Jim Geelen, Bert Gerards, Bruce Reed, Paul Seymour, and Adrian Vetta. On the odd-minor variant of Hadwiger’s conjecture. Journal of Combinatorial Theory, Series B, 99(1):20–29, 2009. https://doi.org/10.1016/j.jctb.2008.03.006.
  6. [6]Carla Groenland, Jesper Nederlof, and Tomohiro Koana. A polynomial time algorithm for Steiner Tree when terminals avoid a rooted K₄-minor. In 19th International Symposium on Parameterized and Exact Computation (IPEC 2024), volume 321 of Leibniz International Proceedings in Informatics (LIPIcs), pages 12:1–12:17, 2024. https://doi.org/10.4230/LIPIcs.IPEC.2024.12.
  7. [7]Andrea Jiménez, Benjamin Moore, Daniel A. Quiroz, and Youngho Yoo. Homomorphism counting for immersion-closed classes is not isomorphism, 2026. Version 2, 14 February 2026. The rendered manuscript title is “Homomorphism counting from a proper immersion-closed class is not isomorphism”. https://arxiv.org/abs/2602.08738v2.
  8. [8]Ken-ichi Kawarabayashi, Serguei Norine, Robin Thomas, and Paul Wollan. K₆ minors in 6-connected graphs of bounded tree-width, 2013. Version 2, 5 April 2013; first posted 9 March 2012. Society definitions in Section 2 and Theorem 2.5. https://arxiv.org/abs/1203.2171v2.
  9. [9]Matthias Kriesell and Samuel Mohr. Kempe chains and rooted minors, 2022. arXiv preprint, version 2, 29 November 2022; first posted 2019. Theta construction: Section 3, pp. 8–9; Theorem 6: Section 5, p. 12. https://arxiv.org/abs/1911.09998v2.
  10. [10]Arnar Á. Kristjánsson. Counterexamples to the strong Robertson conjecture, 2026. Version 1 (arXiv:2610.03550v1), submitted 2 October 2026; theorem and section numbers cited in this work refer to that version. https://arxiv.org/abs/2610.03550; full text: https://arxiv.org/html/2610.03550v1.
  11. [11]Arnar Á. Kristjánsson. Oddomorphisms, split-off minors, and the strong Robertson conjecture, 2026. Version 1, 3 July 2026. https://arxiv.org/abs/2607.03405v1.
  12. [12]Arnar Águst Kristjánsson, Benjamin Moore, Daniel Neuen, David E. Roberson, Tim Seppelt, and Benjamin Young. A proof of the weak Robertson conjecture. Zenodo working paper, 2026. Posted 14 October 2026. Theorem 1.3. https://doi.org/10.5281/zenodo.23370177.
  13. [13]Daniel Neuen and Tim Seppelt. Distinguishing graphs by counting homomorphisms from sparse graphs. In 41st Annual Symposium on Logic in Computer Science (LICS 2026), volume 380 of Leibniz International Proceedings in Informatics (LIPIcs), pages 75:1–75:29, 2026. Published 9 July 2026. Full version: arXiv:2601.18602v2, 10 September 2026, https://arxiv.org/abs/2601.18602v2; lemma numbers cited in this work refer to that arXiv version.
  14. [14]David E. Roberson. Oddomorphisms and homomorphism indistinguishability over graphs of bounded degree. Journal of Combinatorial Theory, Series B, 181:1–61, 2026. Theorem numbering cited in this work is from arXiv:2206.10321v1. https://doi.org/10.1016/j.jctb.2026.07.003.
  15. [15]Neil Robertson and Paul D. Seymour. Graph minors. IX. disjoint crossed paths. Journal of Combinatorial Theory, Series B, 49(1):40–77, 1990. Rural-society consequence of (2.3)–(2.4), in the formulation of Kawarabayashi, Norine, Thomas and Wollan, Theorem 2.5. https://doi.org/10.1016/0095-8956(90)90063-6.
  16. [16]Michal Čertík. Supporting code and certificates for minimum orders of clique oddomorphism counterexamples. Zenodo. https://doi.org/10.5281/zenodo.23603860.

Paper details

vlnc:W_q82ebdhz
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 4

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents