pith. sign in

arxiv: 2607.02159 · v1 · pith:V4QPUG6Snew · submitted 2026-07-02 · 🧮 math.CO · cs.DM

3-Colouring Graphs Excluding a Fixed Minor

Vida Dujmovi\'c , Hussein Houdrouge , Pat Morin This is my paper

Pith reviewed 2026-07-03 10:47 UTC · model grok-4.3

classification 🧮 math.CO cs.DM
keywords clustered coloringminor-closed classes3-coloringgraph minorsclustering boundproper minor-closed
0
0 comments X

The pith

Graphs excluding any fixed minor H admit a 3-coloring with monochromatic components of size at most f(H) n to the 4/9.

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

The paper proves that for every fixed graph H, every n-vertex graph without H as a minor admits a 3-coloring in which each monochromatic connected component has size bounded by a function of H times n raised to the 4/9. This extends a prior result that applied only to planar graphs and improves the previous general bound of order square root of n that held for all minor-closed classes since 2008. A sympathetic reader would care because the result shows that the clustering exponent achieved for planar graphs carries over without change to the much larger family of all proper minor-closed classes.

Core claim

For every fixed graph H, every n-vertex graph G that excludes H as a minor has a vertex colouring with 3 colours in which each monochromatic component has size at most f(H)·n^{4/9}.

What carries the argument

Extension of the structural and coloring techniques developed for planar graphs to the setting of an arbitrary fixed minor H while preserving the 4/9 exponent.

If this is right

  • The result gives the first improvement on clustered 3-colouring of proper minor-closed graph classes since the O_H(sqrt(n)) bound from 2008.
  • The clustering exponent 4/9 is independent of the excluded minor H.
  • The bound applies uniformly to every proper minor-closed graph class.

Where Pith is reading between the lines

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

  • The same techniques might yield analogous clustering bounds for 4-colorings or other bounded-color problems inside minor-closed classes.
  • It remains open whether the exponent 4/9 can be lowered further while keeping the result uniform across all excluded minors.
  • The dependence f(H) may be improvable for specific families of minors H.

Load-bearing premise

The structural and coloring techniques developed for the planar case extend to arbitrary fixed minors H while preserving the 4/9 exponent without additional hidden dependencies on H.

What would settle it

An explicit H-minor-free graph on n vertices for which every 3-coloring contains a monochromatic component whose size exceeds every constant multiple of n to the 4/9.

read the original abstract

We show that, for every fixed graph $H$, every $n$-vertex graph $G$ that excludes $H$ as a minor is $3$-colourable with clustering $O_H(n^{4/9})$. That is, there exists a function $f$ such that for every graph $H$, every $n\ge 1$, every $n$-vertex graph $G$ that excludes $H$ as a minor has a vertex colouring with $3$ colours in which each monochromatic component has size at most $f(H)\cdot n^{4/9}$. This generalizes a recent result of Dujmovi\'c, Morin, Norin, and Wood (\textit{arXiv}:2507.03163) from planar graphs to all proper minor-closed graph classes and is the first improvement on clustered $3$-colouring of proper minor-closed graph classes since the upper bound of $O_H(\sqrt{n})$ due to Linial, Matou\v{s}ek, Sheffet, and Tardos (\textit{Comb. Prob. Comput.}, \textbf{17}(4):577--589, 2008).

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.

Referee Report

0 major / 1 minor

Summary. The manuscript proves that for every fixed graph H, every n-vertex graph G excluding H as a minor admits a 3-colouring in which each monochromatic component has size at most f(H)·n^{4/9}. This generalises the planar clustered 3-colouring result of Dujmović, Morin, Norin and Wood (arXiv:2507.03163) to all proper minor-closed classes while retaining the 4/9 exponent (absorbed into the O_H notation) and improves the previous O_H(√n) upper bound of Linial, Matoušek, Sheffet and Tardos (2008).

Significance. If the central claim holds, the result is a meaningful advance: it is the first improvement on clustered 3-colouring bounds for proper minor-closed classes since 2008 and shows that the planar n^{4/9} exponent extends to arbitrary fixed minors without degradation beyond the allowed H-dependence. The explicit O_H notation and the direct generalisation from the cited planar work are strengths.

minor comments (1)
  1. The abstract states the theorem cleanly but supplies no proof outline, key lemmas, or section references; readers must consult the full manuscript to assess the extension argument.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the accurate summary of our result and for recognizing its significance as the first improvement on clustered 3-colouring bounds for proper minor-closed classes since 2008. The report correctly notes the direct generalisation of the planar n^{4/9} bound from Dujmović et al. (arXiv:2507.03163) while absorbing the H-dependence into the O_H notation. No major comments appear in the report, so we provide no point-by-point responses.

Circularity Check

0 steps flagged

Minor self-citation to planar case; extension is independent

full rationale

The paper generalizes the clustered 3-coloring result of arXiv:2507.03163 (overlapping authors Dujmović and Morin) from planar graphs to H-minor-free graphs while retaining the n^{4/9} exponent (absorbed into f(H)). The abstract and claim present this as an extension of independently established prior work, with no equations, parameter fits, or reductions visible that collapse the bound to inputs by construction. The self-citation is not load-bearing for the new generalization claim, which is the paper's contribution.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result is an asymptotic existence statement in structural graph theory; it introduces no fitted numerical parameters, no new postulated entities, and relies only on standard background facts about minors and colorings.

axioms (1)
  • standard math Standard axioms and closure properties of minor-closed graph classes
    Invoked implicitly when stating that the class is proper and minor-closed for any fixed H.

pith-pipeline@v0.9.1-grok · 5737 in / 1101 out tokens · 39947 ms · 2026-07-03T10:47:34.148307+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

43 extracted references · 31 canonical work pages

  1. [1]

    A separator theorem for nonplanar graphs.Journal of the American Mathematical Society, 3(4):801–808, 1990.doi:10.1090/ S0894-0347-1990-1065053-0

    Noga Alon, Paul Seymour, and Robin Thomas. A separator theorem for nonplanar graphs.Journal of the American Mathematical Society, 3(4):801–808, 1990.doi:10.1090/ S0894-0347-1990-1065053-0

    1990

  2. [2]

    Planar separators.SIAM Journal on Dis- crete Mathematics, 7(2):184–193, 1994.doi:10.1137/S0895480191198768

    Noga Alon, Paul Seymour, and Robin Thomas. Planar separators.SIAM Journal on Dis- crete Mathematics, 7(2):184–193, 1994.doi:10.1137/S0895480191198768

    work page doi:10.1137/s0895480191198768 1994

  3. [3]

    Appel and W

    K.I. Appel and W. Haken.Every Planar Map is Four Colorable. Contemporary mathematics - American Mathematical Society. American Mathematical Society, 1989

    1989

  4. [4]

    Marcin Bria ´nski, Robert Hickingbotham, and David R. Wood. Defective and clustered colouring of graphs with given girth. 2024.2404.14940

    work page arXiv 2024

  5. [5]

    Weak diameter choosability of graphs with an ex- cluded minor.Journal of Combinatorial Theory, Series B, 174:28–70, 2025.doi:https: //doi.org/10.1016/j.jctb.2025.04.005

    Joshua Crouch and Chun-Hung Liu. Weak diameter choosability of graphs with an ex- cluded minor.Journal of Combinatorial Theory, Series B, 174:28–70, 2025.doi:https: //doi.org/10.1016/j.jctb.2025.04.005

    work page doi:10.1016/j.jctb.2025.04.005 2025

  6. [6]

    Demaine, Fedor V

    Erik D. Demaine, Fedor V. Fomin, Mohammad Taghi Hajiaghayi, and Dimitrios M. Thi- likos. Subexponential parameterized algorithms on bounded-genus graphs andH-minor- free graphs.J. ACM, 52(6):866–893, 2005.doi:10.1145/1101821.1101823

    work page doi:10.1145/1101821.1101823 2005

  7. [7]

    On the excluded minor structure theorem for graphs of large tree-width.Journal of Combinato- rial Theory, Series B, 102(6):1189–1210, 2012.doi:https://doi.org/10.1016/j.jctb

    Reinhard Diestel, Ken-ichi Kawarabayashi, Theodor M ¨uller, and Paul Wollan. On the excluded minor structure theorem for graphs of large tree-width.Journal of Combinato- rial Theory, Series B, 102(6):1189–1210, 2012.doi:https://doi.org/10.1016/j.jctb. 2012.07.001

    work page doi:10.1016/j.jctb 2012

  8. [8]

    Vida Dujmovic, Louis Esperet, Pat Morin, and David R. Wood. Proof of the Clustered Hadwiger Conjecture . In2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 1921–1930. IEEE Computer Society, Los Alamitos, CA, USA, 2023. doi:10.1109/FOCS57990.2023.00116

    work page doi:10.1109/focs57990.2023.00116 1921

  9. [9]

    Vida Dujmovi ´c, Louis Esperet, Pat Morin, and David R. Wood. Proof of the clustered Hadwiger conjecture. In64th IEEE Symposium on Foundations of Computer Science, FOCS 2023, Chicago, IL, USA, November 6-9, 2023, pages 1921–1930. IEEE, 2023.doi:10.1109/ FOCS57990.2023.00116

    work page arXiv 2023

  10. [10]

    Vida Dujmovi ´c, Louis Esperet, Pat Morin, Bartosz Walczak, and David R. Wood. Clus- tered 3-colouring graphs of bounded degree.Combinatorics, Probability and Computing, 31(1):123–135, 2022.doi:10.1017/S0963548321000213

    work page doi:10.1017/s0963548321000213 2022

  11. [11]

    Vida Dujmovi ´c, Pat Morin, Sergey Norin, and David R. Wood. 3-colouring planar graphs. 2025.2507.03163

    work page arXiv 2025

  12. [12]

    Testing first-order properties for sub- 17 classes of sparse graphs.Journal of the ACM, 60(5):36:1–36:24, 2013.doi:10.1145/ 2499483

    Zden ˇek Dvoˇr´ak, Daniel Kr ´al’, and Robin Thomas. Testing first-order properties for sub- 17 classes of sparse graphs.Journal of the ACM, 60(5):36:1–36:24, 2013.doi:10.1145/ 2499483

    2013

  13. [13]

    Islands in minor-closed classes

    Zden ˇek Dvoˇr´ak and Sergey Norin. Islands in minor-closed classes. I. bounded treewidth and separators. 2017.1710.02727

    work page arXiv 2017

  14. [14]

    Zden ˇek Dvo ˇr´ak and David R. Wood. Product structure of graph classes with strongly sublinear separators.CoRR, abs/2208.10074, 2022.doi:10.48550/ARXIV.2208.10074. 2208.10074

    work page doi:10.48550/arxiv.2208.10074 2022

  15. [15]

    A relative of Hadwiger’s conjecture.SIAM Journal on Discrete Mathematics, 29(4):2385– 2388, 2015.doi:10.1137/141002177.https://doi.org/10.1137/141002177

    Katherine Edwards, Dong Yeap Kang, Jaehoon Kim, Sang-il Oum, and Paul Seymour. A relative of Hadwiger’s conjecture.SIAM Journal on Discrete Mathematics, 29(4):2385– 2388, 2015.doi:10.1137/141002177.https://doi.org/10.1137/141002177

    work page doi:10.1137/141002177.https://doi.org/10.1137/141002177 2015

  16. [16]

    New upper bounds on harmonious colorings

    Keith Edwards and Colin McDiarmid. New upper bounds on harmonious colorings. Journal of Graph Theory, 18(3):257–267, 1994.doi:https://doi.org/10.1002/jgt. 3190180305.https://onlinelibrary.wiley.com/doi/pdf/10.1002/jgt.3190180305

    work page doi:10.1002/jgt 1994

  17. [17]

    Colouring planar graphs with three colours and no large monochromatic components.Combinatorics Probability and Computing, 23(4):551 – 570, 2014.doi:10.1017/S0963548314000170

    Louis Esperet and Gwena ¨el Joret. Colouring planar graphs with three colours and no large monochromatic components.Combinatorics Probability and Computing, 23(4):551 – 570, 2014.doi:10.1017/S0963548314000170

    work page doi:10.1017/s0963548314000170 2014

  18. [18]

    Embedding grids in surfaces.European Journal of Combinatorics, 25(6):785–792, 2004.doi:https://doi.org/10.1016/j.ejc.2003.07

    J.F Geelen, R.B Richter, and G Salazar. Embedding grids in surfaces.European Journal of Combinatorics, 25(6):785–792, 2004.doi:https://doi.org/10.1016/j.ejc.2003.07

    work page doi:10.1016/j.ejc.2003.07 2004

  19. [19]

    Thematic issue on Topological Graph theory

  20. [20]

    Local tree-width, excluded minors, and approximation algorithms.Com- binatorica, 23(4):613–632, 2003

    Martin Grohe. Local tree-width, excluded minors, and approximation algorithms.Com- binatorica, 23(4):613–632, 2003

    2003

  21. [21]

    Kevin Hendrey and David R. Wood. Defective and clustered choosability of sparse graphs.Combinatorics, Probability and Computing, 28(5):791–810, 2019.doi:10.1017/ S0963548319000063

    2019

  22. [22]

    Jan van den Heuvel and David R. Wood. Improper colourings inspired by Hadwiger’s conjecture.Journal of the London Mathematical Society, 98(1):129–148, 2018.doi:10. 1112/jlms.12127

    2018

  23. [23]

    Robert Hickingbotham, Dong Yeap Kang, Sang il Oum, Raphael Steiner, and David R. Wood. Clustered colouring of odd-h-minor-free graphs. 2024.2308.15721

    work page arXiv 2024

  24. [24]

    Improper colouring of graphs with no odd clique minor.Combinatorics, Probability and Computing, 28(5):740–754, 2019.doi:10.1017/ S0963548318000548

    Dong Yeap Kang and Sang-Il Oum. Improper colouring of graphs with no odd clique minor.Combinatorics, Probability and Computing, 28(5):740–754, 2019.doi:10.1017/ S0963548318000548

    2019

  25. [25]

    A relaxed Hadwiger’s conjecture for list colorings.Journal of Combinatorial Theory, Series B, 97(4):647–651, 2007.doi:https: //doi.org/10.1016/j.jctb.2006.11.002

    Ken ichi Kawarabayashi and Bojan Mohar. A relaxed Hadwiger’s conjecture for list colorings.Journal of Combinatorial Theory, Series B, 97(4):647–651, 2007.doi:https: //doi.org/10.1016/j.jctb.2006.11.002

    work page doi:10.1016/j.jctb.2006.11.002 2007

  26. [26]

    A weakening of the odd Hadwiger’s conjecture.Combinatorics, Probability and Computing, 17(6):815–821, 2008.doi:10.1017/S0963548308009462

    Ken-ichi Kawarabayashi. A weakening of the odd Hadwiger’s conjecture.Combinatorics, Probability and Computing, 17(6):815–821, 2008.doi:10.1017/S0963548308009462

    work page doi:10.1017/s0963548308009462 2008

  27. [27]

    Kleinberg, Rajeev Motwani, Prabhakar Raghavan, and Suresh Venkatasubrama- nian

    Jon M. Kleinberg, Rajeev Motwani, Prabhakar Raghavan, and Suresh Venkatasubrama- nian. Storage management for evolving databases. In38th Annual Symposium on Foun- dations of Computer Science, FOCS 1997, Miami Beach, Florida, USA, October 19-22, 1997, pages 353–362. IEEE Computer Society, 1997.doi:10.1109/SFCS.1997.646124

    work page doi:10.1109/sfcs.1997.646124 1997

  28. [28]

    Graph colouring with no large monochromatic components.Combinatorics, Probability and Computing, 17(4):577–589, 2008.doi:10.1017/S0963548308009140

    Nathan Linial, Jiri Matou ˇsek, OR Sheffet, and Gabor Tardos. Graph colouring with no large monochromatic components.Combinatorics, Probability and Computing, 17(4):577–589, 2008.doi:10.1017/S0963548308009140

    work page doi:10.1017/s0963548308009140 2008

  29. [29]

    Lipton and Robert E

    Richard J. Lipton and Robert E. Tarjan. A separator theorem for planar graphs.SIAM Journal on Applied Mathematics, 36(2):177–189, 1979.doi:10.1137/0136016

    work page doi:10.1137/0136016 1979

  30. [30]

    Defective coloring is perfect for minors.Combinatorica, 44(3):467–507, 2024.doi:10.1007/s00493-024-00081-8

    Chun-Hung Liu. Defective coloring is perfect for minors.Combinatorica, 44(3):467–507, 2024.doi:10.1007/s00493-024-00081-8

    work page doi:10.1007/s00493-024-00081-8 2024

  31. [31]

    Partitioning H-minor free graphs into three subgraphs 18 with no large components.Journal of Combinatorial Theory, Series B, 128:114–133, 2018

    Chun-Hung Liu and Sang il Oum. Partitioning H-minor free graphs into three subgraphs 18 with no large components.Journal of Combinatorial Theory, Series B, 128:114–133, 2018. doi:https://doi.org/10.1016/j.jctb.2017.08.003

    work page doi:10.1016/j.jctb.2017.08.003 2018

  32. [32]

    Chun-Hung Liu and David R. Wood. Clustered coloring of graphs excluding a subgraph and a minor. 2021.1905.09495

    work page arXiv 2021

  33. [33]

    Chun-Hung Liu and David R. Wood. Clustered graph coloring and layered treewidth. 2022.1905.08969

    work page arXiv 2022

  34. [34]

    Chun-Hung Liu and David R. Wood. Clustered variants of Haj ´os’ conjecture.Journal of Combinatorial Theory, Series B, 152:27–54, 2022.doi:https://doi.org/10.1016/j. jctb.2021.09.002

    work page doi:10.1016/j 2022

  35. [35]

    Chun-Hung Liu and David R. Wood. Clustered coloring of graphs with bounded layered treewidth and bounded degree.European Journal of Combinatorics, 122:103730, 2024. doi:https://doi.org/10.1016/j.ejc.2023.103730

    work page doi:10.1016/j.ejc.2023.103730 2024

  36. [36]

    Chun-Hung Liu and David R. Wood. Quasi-tree-partitions of graphs with an excluded subgraph. 2024.2408.00983

    work page arXiv 2024

  37. [37]

    Bojan Mohar, Bruce Reed, and David R. Wood. Colourings with bounded monochro- matic components in graphs of given circumference.Australasian Journal of Combina- torics, 69(2):236–242, 2017

    2017

  38. [38]

    Sergey Norin, Alex Scott, Paul Seymour, and David R. Wood. Clustered colour- ing in minor-closed classes.Combinatorica, 39(6):1387 – 1412, 2019.doi:10.1007/ s00493-019-3848-z. Cited by: 14; All Open Access, Green Open Access

    2019

  39. [39]

    Sergey Norin, Alex Scott, and David R. Wood. Clustered colouring of graph classes with bounded treedepth or pathwidth.Combinatorics, Probability and Computing, 32(1):122–133, 2023.doi:10.1017/S0963548322000165

    work page doi:10.1017/s0963548322000165 2023

  40. [40]

    The four-colour theo- rem.Journal of Combinatorial Theory, Series B, 70(1):2–44, 1997.doi:https://doi.org/ 10.1006/jctb.1997.1750

    Neil Robertson, Daniel Sanders, Paul Seymour, and Robin Thomas. The four-colour theo- rem.Journal of Combinatorial Theory, Series B, 70(1):2–44, 1997.doi:https://doi.org/ 10.1006/jctb.1997.1750

    work page doi:10.1006/jctb.1997.1750 1997

  41. [41]

    Graph minors

    Neil Robertson and Paul D Seymour. Graph minors. II. algorithmic aspects of tree-width. Journal of algorithms, 5(2):226–251, 1984

    1984

  42. [42]

    Graph minors

    Neil Robertson and P .D Seymour. Graph minors. XVI. excluding a non-planar graph. Journal of Combinatorial Theory, Series B, 89(1):43–76, 2003.doi:https://doi.org/10. 1016/S0095-8956(03)00042-X

    2003

  43. [43]

    David R. Wood. Defective and clustered graph colouring. 2018.1803.07694. 19

    work page arXiv 2018