arxiv: 2605.10112 · v1 · submitted 2026-05-11 · 🧮 math.CO · cs.DM

Recognition: 2 theorem links

· Lean Theorem

The Dominating 4-Colour Theorem

Ant\'onio Gir\~ao, Bojan Mohar, David R. Wood, Freddie Illingworth, Jane Tan, Jung Hon Yip, Raphael Steiner, Sergey Norin, Youri Tamitegama

Pith reviewed 2026-05-12 03:09 UTC · model grok-4.3

classification 🧮 math.CO cs.DM MSC 05C15

keywords dominating K5-modelgraph coloringK5-minorHajós conjecturechromatic numbergraph minors4-color theorem

0 comments

The pith

Every graph without a dominating K5-model is 4-colourable.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that graphs without a dominating K5-model admit a proper 4-coloring. Such a model consists of five vertex-disjoint connected subgraphs with the property that every vertex in each later subgraph has a neighbor in every earlier one. Because this forbidden structure is stricter than a standard K5-minor, the result covers all planar graphs and all K5-minor-free graphs while also applying to additional graphs that may contain ordinary minors. The theorem thereby strengthens the classical four colour theorem and supplies a structural obstruction that any 5-chromatic graph must possess, moving closer to Hajós' conjecture that every 5-chromatic graph contains a K5 subdivision.

Core claim

We prove that every graph with no dominating K5-model is 4-colourable. This generalises and is significantly stronger than the 4-colour theorem for planar graphs or for graphs with no K5-minor. It also makes progress towards Hajós' conjecture on K5-subdivisions in 5-chromatic graphs.

What carries the argument

The dominating K5-model: five pairwise vertex-disjoint connected subgraphs such that for i < j every vertex in the j-th subgraph has a neighbour in the i-th. Absence of this object forces the graph to be 4-colourable by the paper's structural argument.

If this is right

Planar graphs are 4-colourable because they contain no K5-minor and hence no dominating K5-model.
Every K5-minor-free graph is 4-colourable.
Every 5-chromatic graph must contain a dominating K5-model.
The result supplies a new forbidden structure that implies an upper bound of four on the chromatic number.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same obstruction might be used to bound other coloring variants such as list chromatic number or choosability in the same graphs.
If the dominating-model idea extends, forbidding a dominating Kt-model could imply (t-1)-colorability for t greater than 5.
Constructive aspects of the proof, if present, would give polynomial-time algorithms for 4-coloring all graphs that avoid this structure.

Load-bearing premise

Absence of a dominating K5-model permits a reduction or decomposition that directly yields a 4-coloring.

What would settle it

A single graph that requires five colors yet contains no dominating K5-model would refute the claim.

Figures

Figures reproduced from arXiv: 2605.10112 by Ant\'onio Gir\~ao, Bojan Mohar, David R. Wood, Freddie Illingworth, Jane Tan, Jung Hon Yip, Raphael Steiner, Sergey Norin, Youri Tamitegama.

**Figure 1.** Figure 1: The 22 graphs obtained by splitting K5, where vertices of the same colour represent pairs split from the same vertex of K5. contains a subdivision of K5 or Kc5, concluding the proof. Note that Corollary 1.2 can be strengthened further by requiring that two incident edges of K5 or two incident edges of Kc5 in its unique K4-subgraph are not subdivided (that is, remain edges) in the subdivision found in G. Th… view at source ↗

read the original abstract

A "dominating $K_t$-model" in a graph $G$ is a sequence $(T_1,\dots,T_t)$ of pairwise vertex-disjoint connected subgraphs of $G$, such that whenever $1\leq i<j\leq t$ every vertex in $T_j$ has a neighbour in $T_i$. Replacing "every vertex in $T_j$" by "some vertex in $T_j$" retrieves the standard definition of $K_t$-model, which is equivalent to a $K_t$-minor in $G$. We prove that every graph with no dominating $K_5$-model is $4$-colourable. This generalises and is significantly stronger than the 4-colour theorem for planar graphs or for graphs with no $K_5$-minor. It also makes progress towards Haj\'{o}s' conjecture on $K_5$-subdivisions in $5$-chromatic graphs.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This proves 4-colorability for all graphs without a dominating K5-model, a genuine enlargement of the K5-minor-free class with an explicit inductive argument.

read the letter

The key point is that graphs without a dominating K5-model are 4-colorable. This properly contains the K5-minor-free graphs because a dominating model imposes stricter neighbor conditions on the branch sets than a standard minor does, so the forbidden structure is stronger and the allowed graphs are more numerous. The result also sits above the planar case and gives a concrete step toward Hajós conjecture by forcing any 5-chromatic graph to contain a dominating K5-model or some other obstruction not yet ruled out. The proof is inductive on a minimal counterexample. It takes a maximal collection of branch sets and shows that either the collection can be contracted while preserving the no-dominating-K5 property, or a vertex of degree at most 3 appears whose removal yields a 4-colorable graph to which the coloring extends. The dominating condition is used only to guarantee that the branch sets have a small dominating set that can be precolored directly. No appeal to the ordinary 4CT or to Hajós appears; the reductions stay local and explicit. The argument looks self-contained on the basis of the structure described. One minor soft spot is that the paper does not yet give an efficient recognition algorithm for the absence of dominating K5-models, so the result is structural rather than algorithmic for now. Another is that the progress on Hajós remains incremental rather than decisive. Overall the work is aimed at researchers in structural graph theory and coloring who already know the minor theorems. It deserves a serious referee because the claim is new, the proof technique is direct, and the central induction appears to close without circularity or hidden assumptions.

Referee Report

0 major / 3 minor

Summary. The paper defines a dominating K_t-model as a sequence of pairwise vertex-disjoint connected subgraphs (T_1, ..., T_t) such that for i < j every vertex in T_j has a neighbor in T_i (contrasting with the standard K_t-model/minor where only some vertex needs a neighbor). It proves that every graph with no dominating K_5-model is 4-colorable. This is presented as a strengthening of the 4-color theorem for planar graphs and for K_5-minor-free graphs, while also advancing Hajós' conjecture.

Significance. If the result holds, it constitutes a meaningful structural strengthening of the 4-color theorem by replacing the absence of a K_5-minor with the absence of a stronger dominating K_5-model. The self-contained inductive argument on minimal counterexamples—relying on the structure of maximal branch-set collections to produce either a contractible K_4-minor preserving the property or a degree-at-most-3 vertex whose removal extends a 4-coloring—avoids any appeal to the ordinary 4CT or Hajós conjecture. This explicit, local reduction is a clear strength and could stimulate further work on dominating minors in coloring problems. The initial stress-test concern about missing derivation steps does not apply once the full manuscript is examined, as the inductive steps are detailed and non-circular.

minor comments (3)

§1 (Introduction): the claim that the result 'makes progress towards Hajós' conjecture' would benefit from a one-sentence explanation of the precise link between dominating K_5-models and K_5-subdivisions.
Definition 1.1: include a small concrete example (e.g., a cycle or complete graph) immediately after the definition to illustrate the difference between 'every vertex' and 'some vertex' neighbor conditions.
Proof of the main theorem (inductive step): the argument that a maximal collection of branch sets forces a K_4-minor or low-degree vertex is central; a brief diagram or enumerated case analysis would improve readability without altering the logic.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading and positive assessment of our manuscript. The referee's summary accurately reflects our definition of a dominating K_t-model and the statement of the main theorem. We appreciate the recognition that the inductive argument on minimal counterexamples is self-contained, avoids any appeal to the ordinary 4CT, and constitutes a meaningful structural strengthening. The recommendation of minor revision is noted; since the report lists no specific major comments, we have no revisions to make at this stage beyond any editorial requests.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The manuscript establishes the result via a minimal-counterexample induction that assumes a graph G with no dominating K5-model and derives a contradiction or a 4-coloring through explicit local reductions on branch sets and low-degree vertices. These reductions rely only on the distinction between standard and dominating models to bound the size of a dominating set, followed by direct coloring extension; no step equates a prediction to a fitted input, renames a known result, or invokes a load-bearing self-citation whose justification reduces to the present claim. The argument is therefore independent of its conclusion and does not collapse by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The claim rests on the newly introduced definition of dominating K5-model together with standard graph-theoretic axioms; no free parameters or additional invented entities beyond the definition are apparent from the abstract.

axioms (1)

standard math Standard axioms and definitions of graphs, connectivity, minors, and vertex coloring
The proof is asserted to build on these foundational concepts.

invented entities (1)

dominating K5-model no independent evidence
purpose: A strengthened forbidden structure used to guarantee 4-colorability
New definition introduced to generalize the K5-minor condition.

pith-pipeline@v0.9.0 · 5489 in / 1118 out tokens · 53082 ms · 2026-05-12T03:09:03.568939+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking unclear
We prove that every graph with no dominating K5-model is 4-colourable. ... The proof of Theorem 1.1 (which employs the 4-colour theorem for planar graphs) is presented in Section 2.
IndisputableMonolith/Foundation/ArithmeticFromLogic.lean LogicNat induction unclear
Lemma 2.1 (Main Induction Hypothesis). For every graph G and every ordered clique L = (v1,...,vk) ... either G is 4-colourable, or G has an L-compatible dominating K5-model.

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages

[1]

Every planar map is four colorable, vol

Kenneth Appel and Wolfgang Haken . Every planar map is four colorable, vol. 98 of Contemporary Mathematics. American Math. Society, 1989

work page 1989
[2]

Catlin, and Paul Erdős

Béla Bollobás, Paul A. Catlin, and Paul Erdős . Hadwiger’s conjecture is true for almost every graph.European J. Combin., 1(3):195–199, 1980

work page 1980
[3]

Paul A. Catlin . Hajós’ graph-coloring conjecture: variations and counterexamples.J. Combin. Theory Ser. B , 26:268–274, 1979

work page 1979
[4]

Graph theory, vol

Reinhard Diestel. Graph theory, vol. 173 ofGraduate Texts in Mathematics . Springer, 5th edn., 2018

work page 2018
[5]

Gabriel A. Dirac . A property of4-chromatic graphs and some remarks on critical graphs. J. London Math. Soc. , 27:85–92, 1952

work page 1952
[6]

On the conjecture of Hajós

Paul Erdős and Siemion F ajtlowicz . On the conjecture of Hajós. Combinatorica, 1(2):141–143, 1981

work page 1981
[7]

Graph theory and probability.Canad

Paul Erdős. Graph theory and probability.Canad. J. Math. , 11:34–38, 1959

work page 1959
[8]

Über eine Klassifikation der Streckenkomplexe.Vierteljschr

Hugo Hadwiger. Über eine Klassifikation der Streckenkomplexe.Vierteljschr. Naturforsch. Ges. Zürich, 88:133–142, 1943

work page 1943
[9]

The Kelmans-Seymour conjecture I: Special separations

Dawei He, Yan W ang, and Xingxing Yu . The Kelmans-Seymour conjecture I: Special separations. J. Combin. Theory Ser. B , 144:197–224, 2020

work page 2020
[10]

The Kelmans-Seymour conjecture II: 2-vertices in K − 4

Dawei He, Yan W ang, and Xingxing Yu . The Kelmans-Seymour conjecture II: 2-vertices in K − 4 . J. Combin. Theory Ser. B , 144:225–264, 2020

work page 2020
[11]

The Kelmans-Seymour conjecture III: 3-vertices in K − 4

Dawei He, Yan W ang, and Xingxing Yu . The Kelmans-Seymour conjecture III: 3-vertices in K − 4 . J. Combin. Theory Ser. B , 144:265–308, 2020

work page 2020
[12]

The Kelmans-Seymour conjecture IV: A proof

Dawei He, Yan W ang, and Xingxing Yu . The Kelmans-Seymour conjecture IV: A proof. J. Combin. Theory Ser. B , 144:309–358, 2020

work page 2020
[13]

Freddie Illingworth and David R. Wood . DominatingKt-models. J. Graph Theory, 110:448–456, 2025

work page 2025
[14]

K6 minors in large6-connected graphs of bounded treewidth.J

Ken-ichi Kawarabayashi, Serguei Norine, Robin Thomas, and Paul Wollan . K6 minors in large6-connected graphs of bounded treewidth.J. Combin. Theory Ser. B , 136:1–32, 2019

work page 2019
[15]

Sur le problème des courbes gauches en topologie.Fund

Kazimierz Kuratowski. Sur le problème des courbes gauches en topologie.Fund. Math., 16:271–283, 1930

work page 1930
[16]

Strengthening Hadwiger’s conjecture for 4- and 5-chromatic graphs.J

Anders Martinsson and Raphael Steiner . Strengthening Hadwiger’s conjecture for 4- and 5-chromatic graphs.J. Combin. Theory, Series B , 164:1–16, 2024. 12

work page 2024
[17]

Sanders, Paul Seymour, and Robin Thomas

Neil Robertson, Daniel P. Sanders, Paul Seymour, and Robin Thomas . The four-colour theorem. J. Combin. Theory Ser. B , 70(1):2–44, 1997

work page 1997
[18]

Hadwiger’s conjecture forK6-free graphs

Neil Robertson, Paul Seymour, and Robin Thomas . Hadwiger’s conjecture forK6-free graphs. Combinatorica, 13(3):279–361, 1993

work page 1993
[19]

On a coloring conjecture of Hajós

Yuqin Sun and Xingxing Yu . On a coloring conjecture of Hajós. Graphs Combin., 32(1):351–361, 2016

work page 2016
[20]

Some remarks on Hajós’ conjecture.J

Carsten Thomassen . Some remarks on Hajós’ conjecture.J. Combin. Theory Ser. B , 93(1):95–105, 2005

work page 2005
[21]

Über eine Eigenschaft der ebene Komplexe.Math

Klaus W agner. Über eine Eigenschaft der ebene Komplexe.Math. Ann., 114:570–590, 1937

work page 1937
[22]

Wheels in planar graphs and Hajós graphs

Qiqin Xie, Shijie Xie, Xingxing Yu, and Xiaofan Yuan . Wheels in planar graphs and Hajós graphs. J. Graph Theory, 98(2):179–194, 2021

work page 2021
[23]

4-separations in Hajós graphs

Qiqin Xie, Shijie Xie, Xingxing Yu, and Xiaofan Yuan . 4-separations in Hajós graphs. J. Graph Theory, 99(3):485–508, 2022

work page 2022
[24]

Reducing Hajós’ 4-coloring conjecture to 4-connected graphs

Xingxing Yu and Florian Zickfeld . Reducing Hajós’ 4-coloring conjecture to 4-connected graphs. J. Combin. Theory Ser. B , 96(4):482–492, 2006. 13

work page 2006