Minimum orders of clique oddomorphism counterexamples
Abstract
An oddomorphism to Kn 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 Kn on at most n+6 vertices contains a Kn 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≥8 the minimum order of a graph admitting a weak oddomorphism to Kn but having no Kn minor is exactly n+7. The extremal example is a fifteen-vertex graph with an oddomorphism to K8, 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 K8 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.
Related
- Counterexamples to two conjectures on the diameter of clique-free graphs
- An improved minimum degree threshold for fractional clique decompositions in partite graphs
- Bounded chromatic number of graphs with small clique number and large minimum degree
- Counterexamples to additivity of minimum output p-Rényi entropy of quantum channels for all p≥ 0
- A Sublinear Minimum-Degree Condition for $2$-Connected Subgraphs of All Orders
BibTeX
@misc{certik2026minimum,
title = {{Minimum orders of clique oddomorphism counterexamples}},
author = {Michal Čertík},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.33283},
eprint = {2610.33283},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.33283},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Minimum orders of clique oddomorphism counterexamples
AU - Michal Čertík
PY - 2026
DA - 2026/10/23
PB - arXiv
DO - 10.48550/arxiv.2610.33283
UR - https://arxiv.org/abs/2610.33283
AB - 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≥8 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.
ER -