3-Colouring Planar Graphs

David R. Wood; Pat Morin; Sergey Norin; Vida Dujmovi\'c

REVIEW 3 major objections 4 minor 1 cited by

3-Colouring Planar Graphs

T0 review · 3 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Every n-vertex planar graph is 3-colourable with clustering O(n^{4/9}), improving the previous O(n^{1/2}) bound.

desk verdict A real improvement on clustered 3-colouring of planar graphs, with a genuine gap in the key induction of Lemma 10 that needs fixing. read the letter →

arxiv 2507.03163 v2 pith:TXPKKM5I submitted 2025-07-03 math.CO cs.DM

Vida Dujmović , Pat Morin , Sergey Norin , David R. Wood This is my paper · ORCID

classification math.COcs.DM MSC 05C1505C1005C83

keywords planargraphsclusteredcolouring3-colouringmonochromaticcomponentstreewidthgraphseparatorsgridminorsface-weighting

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper proves that every planar graph on n vertices can be coloured with three colours so that every connected monochromatic component has at most O($n^{{4/9}}$) vertices, improving the previous best guarantee of O($n^{{1/2}}$). Such a clustered colouring is the standard relaxation of proper colouring when only three colours are allowed, since the Four-Colour Theorem prohibits exact 3-colouring of many planar graphs. The result narrows the gap between the known lower bound $\Omega(n^{1/3})$ and the best upper bound, and the proof introduces a separator construction of independent interest: a q-separator whose induced subgraph has treewidth only $O((n/q)^{1/2})$, not the naive $O(n^{1/2}/q^{1/4})$.

What carries the argument

The engine is a face-weighting lemma (Lemma 10) that recursively cuts a connected subgraph along nooses, which are simple closed curves made of graph edges. The faces of a subgraph are weighted by the number of original vertices lying inside them; each cut is chosen by a weighted cycle-separator lemma so that the weight on every resulting component drops by at least a factor of $2/3$, while the number of faces that are new, meaning not inherited from the original graph, increases by at most one. This tradeoff, weight dropping geometrically while the hole count grows only linearly, yields the bound $|X_C| \le \log_{3/2} N$ that controls both the size and the treewidth of the separator. An embedding-preserving triangulation step and the linear grid-minor/treewidth bound for planar graphs, $\mathrm{tw}(G) \le 6\,\mathrm{gm}(G)+1$, are the planarity-specific ingredients that make the weighted separator possible.

What would settle it

Exhibit a connected plane graph $C$, a face-weighting, and a noose such that some component of $C$ minus the noose contains two or more faces that are not faces of $C$, while the total weight on that component is still above $2/3$ of the weight of $C$; that would directly violate the $|X_{C'}| \le |X_C| + 1$ step in Lemma 10 and invalidate the stated proof of the $O(n^{4/9})$ bound.

Watch

Extended reading notes

Core claim

The central claim is that the clustered three-colouring problem for planar graphs admits a bound of $O(n^{4/9})$, not the $O(n^{1/2})$ obtained by repeatedly applying a single separator theorem. The proof chooses a first separator $S_0$ of size $O(n^{7/9})$ so that the red colour class has no large components, then shows that the graph induced on $S_0$ itself admits a separator $S_1$ of size $O(n^{4/9})$ after which the remaining graph has treewidth $O(n^{1/9})$; a final separator of size $O(n^{4/9})$ in that bounded-treewidth graph colours the remaining vertices blue, while $S_1$ together with the final separator, coloured yellow, has at most $O(n^{4/9})$ vertices. For sufficiently large $n$, the constant is explicit: the paper states a clustering bound of $16 n^{4/9}$.

Load-bearing premise

The bound rests on the claim that cutting a component along a noose adds at most one new face that was not already a face of that component, so the number of such faces grows at most linearly through the recursive cuts; if one cut could create many new faces, the induction behind Lemma 10, and hence the constant 16, would collapse.

Editorial extensions

If this is right

The clustered 3-colouring upper bound for planar graphs drops from $O(n^{1/2})$ to $O(n^{4/9})$, leaving a gap between that upper bound and the known $\Omega(n^{1/3})$ lower bound.
The proof yields an explicit separator with $|S| = O(n/q^{1/2})$ and $\mathrm{tw}(G[S]) = O((n/q)^{1/2})$ for every $q$, which is best possible up to constants by the grid example given in the paper.
Because all constants in the proof are explicit, the construction is in principle algorithmic: finding the separators and colouring the remaining bounded-treewidth graph gives the claimed clustering.
The face-weighting lemma applies to any plane graph and any non-negative face weights, so the separator result is not tied to the specific colouring application and can be used wherever weighted planar separation is needed.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The exponent $4/9$ is tied to the $2/3$ weight drop and the at-most-one-new-face induction; a stronger control on new faces would plausibly lower the exponent, so the gap to $n^{1/3}$ is a natural target for future work.
The same template may extend to other minor-closed classes that have a linear bound between treewidth and grid minors, such as graphs on surfaces of bounded genus; if the embedding-preserving triangulation step can be adapted, a similar $O(n^{4/9})$ clustering could follow there.
One could test Lemma 10 computationally on random plane triangulations: search for a noose whose removal creates two or more new faces in a component; if found, the proof's constant would need repair even if the theorem itself survives.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Colleague,

The headline is that this paper gives a real improvement on the clustered 3-colouring bound for planar graphs, from O(n^{1/2}) to O(n^{4/9}), and the face-weighting separator machinery is honest work. But the central proof step in Lemma 10 has a gap that is not a typo. The paper assumes you can go from N_C ≤ (2/3)^{|X_C|}N to |X_C| ≤ log_{3/2}N, which requires N_C > 0. That positivity is never established, and the hypotheses allow N_C=0. Take a grid, put an extra vertex inside every cell so it becomes a triangulation with the grid edges intact, then move all those extra vertices into the separator S. The remaining component is the grid; every one of its faces is a hole, so N_C=0 and |X_C| is the number of cells, which is about k^2, while log_{3/2}N is about 2 log k. The inference fails. This matters because (3) and the bound on |C_i| use that log bound to charge holes against face weight.

The rest of the paper holds up better. Lemma 5, giving a q-separator whose induced subgraph has small grid minor, is a good observation and the proof is clean. Lemma 4's constant is off: the geometric sum evaluates to about 23.1, not 12, but that only changes constants. The citation pattern looks fine; the prior bound from Linial et al. is correctly credited.

So where does that leave the theorem? Not proven as written. The gap may be fixable—perhaps one can argue that components with N_C=0 have small treewidth for other reasons, or redefine the weighting—but as it stands the main induction doesn't close. I would send this to a serious referee, because the idea is strong and the result is important, but I would not take it as a proof yet. I'd want to see a repair of Lemma 10 that excludes or handles the zero-weight case.

My reading-group vote is yes; there is a lot of usable technique here even if the paper needs revision.

Referee Report

3 major / 4 minor

Summary. The paper proves that every n-vertex planar graph admits a 3-colouring in which every monochromatic component has O(n^{4/9}) vertices, improving the previous O(n^{1/2}) upper bound of Linial, Matoušek, Sheffet, and Tardos. The proof develops separator and treewidth tools for planar graphs: Lemma 5 gives a q-separator whose induced subgraph has small treewidth; Lemmas 6--9 give weighted noose and cycle separators with explicit constants; Lemma 10 iterates these to remove a set S with |S| = O((N/W)t^{-1} + (N/W)t^{-2}) and tw(G-S) < t; Theorem 11 combines Lemma 10 with a separator lemma of Dvořák and Wood to obtain the final clustered 3-colouring. The paper is self-contained apart from standard external theorems and includes explicit, though non-optimised, constants.

Significance. If the main theorem is correct, it is a genuine advance on a well-known open problem in clustered colouring, and the separator/treewidth lemmas (especially Lemmas 5 and 6) are of independent interest. The proof strategy is natural and the auxiliary lemmas are mostly well argued; the paper also clearly identifies the previous lower bound and the gap that remains. However, the central engine, Lemma 10, has a serious gap concerning components with zero face-weight, and a separate inequality error in the bucketing argument. As written, the proof of the main theorem is not complete. The errors appear local enough that the asymptotic result may be repairable, but substantial work is needed in Lemma 10.

major comments (3)

[Lemma 4] The final geometric sum is evaluated incorrectly. With c = 3√2, the displayed series equals c · √(3/2) / (√(3/2) − 1) = 9√2 + 6√3 ≈ 23.12, not < 12. Consequently the stated bound |S| ≤ 12n/q^{1/2} is not justified, and the subsequent numerical claims in Lemma 5 and Theorem 11 (e.g., |S0| ≤ 3n^{7/9} and the constant 16 in the clustering bound) are not established with the displayed constants. The asymptotic O(n^{4/9}) conclusion would survive if all constants are enlarged, but the explicit-constant statements need correction.
[Lemma 10, after Eq. (2)] The inference |X_C| ≤ log_{3/2}(N/N_C) ≤ log_{3/2}N divides by N_C and therefore requires N_C > 0. The proof never establishes N_C > 0 for every processed component. A component C with N_C = 0 is compatible with the stated hypotheses: for instance, take a large grid component whose faces are all non-original holes, with the original face-weighting assigned to removed vertices. In such a case Lemma 6 gives no contradiction, and the later inequality (3), N_C/W ≥ 36 + 9|X_C|, cannot hold. Since (3) and the subsequent bucket estimates control the total separator size, the central bound is unsupported without an additional argument excluding or otherwise handling zero-weight components. The concern raised in the reader's report about |X_{C'}| ≤ |X_C| + 1 is secondary; even granting that bound, the log estimate fails when N_C = 0.
[Lemma 10, bucketing after Eq. (3)] The level-monotonicity claim is reversed. From (3) the proof obtains M_C > (4/3)M_{C'} for a child C′, where M_C = |X_C| + N_C/W. For C ∈ C_i, M_C < A(4/3)^{i+1} with A = (t−7)^2/144, so M_{C′} < A(4/3)^i; hence C′ lies in C_j with j ≤ i−1, not j ≥ i+1 as stated. The conclusion that distinct C,D ∈ C_i satisfy F(C) ∩ F(D) ∩ F(G) = ∅ is therefore not obtained by the argument given, even though it may be recoverable from the opposite inequality. This is load-bearing because the bound |C_i| ≤ 160N/(W(t−7)^2)(3/4)^i relies on the claimed disjointness.

minor comments (4)

[Lemma 9] In the sentence 'any component C of G−V(λ) is contained in some component C′ of G−V(λ)', the second graph should be G′−V(λ).
[Theorem 11] The inequality |V(G2)|(k+1) ≤ |S|t is not valid for non-integer t, since k+1 can equal t+1. The application of Lemma 2 can be repaired by using k+1 ≤ t+1 and the fact that the estimate holds for sufficiently large n, but the displayed inequality should be corrected.
[Lemma 10] The collection of processed components and a generic component are both denoted by C, which makes the paragraph after (2) hard to read; using a different symbol for the collection would improve clarity.
[Lemma 4] The phrase 'Each level 1 component has more than q vertices' is only true for components that are actually separated; the level definition could be phrased more explicitly to avoid confusion.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the proof is a self-contained derivation from standard separator/treewidth results; the only author self-citation (Lemma 2 from [14]) is independent, parameter-free, and not fitted to the target.

full rationale

The derivation chain in Theorem 11 is: Lemma 4 (proved in the paper from Alon–Seymour–Thomas planar separators), Lemma 6 (proved in the paper), Lemma 7 (an adaptation of Alon et al.), Lemma 8 (proved in the paper), Lemma 9 (proved from Lemmas 7 and 8), Lemma 10 (proved from Lemmas 6 and 9), and finally Theorem 11. The only externally cited ingredients are standard or independent: Lemma 3 (Robertson–Seymour–Thomas grid/treewidth theorem), Lemma 2 (Dvořák–Wood [14, Lemma 25]), and the Lipton–Tarjan separator theorem. Although [14] shares an author with the present paper, Lemma 2 is a general, parameter-free statement about q-separators and treewidth; its assumptions do not mention 3-colouring, clustering, or monochromatic components, and no quantity in Lemma 2 is fitted to the O(n^{4/9}) bound. Thus it is independent support rather than a self-citation that carries the argument by assertion. No equation in the paper is equivalent to the target by construction: the clustering bound 16n^{4/9} arises from the explicit separator sizes, not from a definition of those separators in terms of the conclusion. There is no fitted parameter renamed as a prediction, no uniqueness theorem imported from the authors' prior work, and no ansatz smuggled in via citation. The skeptic's concern about Lemma 10 dividing by N_C (which could be zero) is a possible correctness or edge-case gap in the induction, but it is not a circularity: even if the bound |X_C| ≤ log_{3/2}N is unsupported in some cases, the claim is not made true by definition or by self-reference. The paper's explicit constants and proofs of Lemmas 6–10 make the main derivation self-contained. Score 0.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The proof uses only standard graph theory results and previously published separator/treewidth lemmas, many with proofs in the paper. No free parameters are fit to data; the explicit constants are chosen to satisfy inequalities and do not affect the asymptotic claim. No new entities are introduced.

assumptions (6)

standard math Alon-Seymour-Thomas planar separator theorem: every n-vertex planar graph has a 2n/3-separator of size at most c*sqrt(n) with c=3*sqrt(2).
Used in Lemma 4 to obtain q-separators; quoted from [2]. The paper's own Lemma 4 proof re-derives the geometric sum, but the initial separator is an external black box.
standard math Robertson-Seymour-Thomas linear grid minor theorem: for planar graphs, tw(G) <= 6 gm(G) + 1.
Used in Lemmas 3, 5, 6, 7 to convert grid minors to treewidth and vice versa; cited from [43].
domain assumption Dvorak-Wood Lemma 2: if n(k+1) <= pq and p >= k+1, then an n-vertex graph of treewidth <= k has a q-separator of size <= p.
Applied to G2 in Theorem 11; cited from [14], a paper co-authored by the present author Wood. Not proven here.
standard math Menger's theorem: if every A-B separator has size >= t, then there are t vertex-disjoint A-B paths.
Used in Lemma 7 to obtain t disjoint paths and a grid minor.
domain assumption Minimal separators in planar triangulations are cycles.
Used in Lemma 7's footnote to show G^-[X] is connected; cited from Mohar-Thomassen [35, Prop 8.2.3].
standard math Chordal graphs are exactly graphs with a tree-decomposition whose bags are cliques.
Used in Lemma 8 to argue H is a maximal outerplanar graph; cited from Diestel [8].

how reviews work

0 comments

Cite this review

Pith. "Pith review of 3-Colouring Planar Graphs." pith.science (2026). https://pith.science/paper/TXPKKM5I

@misc{pith2026250703163,
  author       = {Pith},
  title        = {Pith review of: 3-Colouring Planar Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TXPKKM5I}},
  note         = {Machine review of arXiv:2507.03163}
}

abstract

We show that every $n$-vertex planar graph is 3-colourable with monochromatic components of size $O(n^{4/9})$. The best previous bound was $O(n^{1/2})$ due to Linial, Matou\v{s}ek, Sheffet and Tardos [Combin. Probab. Comput., 2008].

Figures

Figures reproduced from arXiv: 2507.03163 by the authors.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Optimal tree-decompositions with bags of bounded pathwidth
math.CO 2026-07 accept novelty 7.0 of 10

Every planar graph admits an optimal tree-decomposition in which every bag induces a subgraph of pathwidth at most 3, with an O(k) bound on unions of k bags, and analogues for fixed-surface graphs.

Reference graph

Works this paper leans on

45 extracted references · 32 canonical work pages · cited by 1 Pith paper

[1]

A separator theorem for nonplanar graphs

Noga Alon, Paul Seymour, and Robin Thomas . A separator theorem for nonplanar graphs. J. Amer. Math. Soc., 3(4):801–808, 1990

1990
[2]

Planar separators.SIAM J

Noga Alon, Paul Seymour, and Robin Thomas . Planar separators.SIAM J. Discrete Math., 7(2):184–193, 1994

work page 1994
[3]

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

1989
[4]

Drawing planar 3-trees with given face areas

Therese Biedl and Lesvia Elena Ruiz Velázquez . Drawing planar 3-trees with given face areas. Comput. Geom., 46(3):276–285, 2013

work page 2013
[5]

Bodlaender

Hans L. Bodlaender . A partialk-arboretum of graphs with bounded treewidth.Theoret. Comput. Sci., 209(1-2):1–45, 1998

1998
[6]

Marcin Briański, Robert Hickingbotham, and David R. Wood . Defective and clustered colouring of graphs with given girth. 2024, arXiv:2404.14940

work page arXiv 2024
[7]

Weak diameter choosability of graphs with an excluded minor

Joshua Crouch and Chun-Hung Liu . Weak diameter choosability of graphs with an excluded minor. J. Combin. Theory Ser. B, 174:28–70, 2025

work page 2025
[8]

Graph theory, vol

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

work page 2018

Show all 45 references

[9]

Vida Dujmović, Louis Esperet, Pat Morin, Bartosz W alczak, and David R. Wood . Clustered 3-colouring graphs of bounded degree.Combin. Probab. Comput., 31(1):123–135, 2022

2022
[10]

Vida Dujmović, Louis Esperet, Pat Morin, and David R. Wood . Proof of the clustered Hadwiger conjecture. InProc. 64th IEEE Annual Symposium on Foundations of Computer Science (FOCS ’23), pp. 1921–1930. 2023. ArXiv:2306.06224

1921 arXiv
[11]

Vida Dujmović, Pat Morin, and David R. Wood . Layered separators in minor-closed graph classes with applications.J. Combin. Theory Ser. B, 127:111–147, 2017. arXiv:1306.1595

2017 arXiv
[12]

Islands in minor-closed classes

Zdeněk Dvořák and Sergey Norin . Islands in minor-closed classes. I. Bounded treewidth and separators. 2017, arXiv:1710.02727

2017 arXiv
[13]

Treewidth of graphs with balanced separations.J

Zdeněk Dvořák and Sergey Norin . Treewidth of graphs with balanced separations.J. Combin. Theory Ser. B, 137:137–144, 2019

2019
[14]

Zdeněk Dvořák and David R. Wood . Product structure of graph classes with strongly sublinear separators. 2022, arXiv:2208.10074

2022 arXiv
[15]

A relative of Hadwiger’s conjecture.SIAM J

Katherine Edwards, Dong Yeap Kang, Jaehoon Kim, Sang-il Oum, and Paul Seymour. A relative of Hadwiger’s conjecture.SIAM J. Discrete Math., 29(4):2385–2388, 2015

2015
[16]

Harvey and David R

Daniel J. Harvey and David R. Wood . Parameters tied to treewidth.J. Graph Theory, 84(4):364–385, 2017

2017
[17]

Kevin Hendrey and David R. Wood . Defective and clustered colouring of sparse graphs. Combin. Probab. Comput., 28(5):791–810, 2019

2019
[18]

Robert Hickingbotham, Dong Yeap Kang, Sang il Oum, Raphael Steiner, and David R. Wood . Clustered colouring of odd-H-minor-free graphs. In David R. Wood, Alison Etheridge, Jan de Gier, and Nalini Joshi , eds.,2023 MATRIX Annals, p. to appear. Springer, 2025. ArXiv:2308.15721

2023 arXiv
[19]

Separation number and treewidth, revisited

Hussein Houdrouge, Babak Miraftab, and Pat Morin . Separation number and treewidth, revisited. 2025, arXiv:2503.17112

2025 arXiv
[20]

Improper coloring of graphs with no odd clique minor

Dong Yeap Kang and Sang-il Oum . Improper coloring of graphs with no odd clique minor. Combin. Probab. Comput., 28(5):740–754, 2019. 12

2019
[21]

A weakening of the odd Hadwiger’s conjecture.Combin

Ken-ichi Kawarabayashi. A weakening of the odd Hadwiger’s conjecture.Combin. Probab. Comput., 17(6):815–821, 2008

2008
[22]

A relaxed Hadwiger’s conjecture for list colorings

Ken-ichi Kawarabayashi and Bojan Mohar . A relaxed Hadwiger’s conjecture for list colorings. J. Combin. Theory Ser. B, 97(4):647–651, 2007

2007
[23]

Kleinberg, Rajeev Motwani, Prabhakar Raghavan, and Suresh Venkata- subramanian

Jon M. Kleinberg, Rajeev Motwani, Prabhakar Raghavan, and Suresh Venkata- subramanian. Storage management for evolving databases. In 38th Annual Symp. on Foundations of Computer Science(FOCS ’97), pp. 353–362. IEEE, 1997

1997
[24]

Graph colouring with no large monochromatic components.Combin

Nathan Linial, Jiří Matoušek, Or Sheffet, and Gábor Tardos . Graph colouring with no large monochromatic components.Combin. Probab. Comput., 17(4):577–589, 2008

2008
[25]

Lipton and Robert E

Richard J. Lipton and Robert E. Tarjan . A separator theorem for planar graphs.SIAM J. Appl. Math., 36(2):177–189, 1979

1979
[26]

Lipton and Robert E

Richard J. Lipton and Robert E. Tarjan . Applications of a planar separator theorem. SIAM J. Comput., 9(3):615–627, 1980

1980
[27]

Defective coloring is perfect for minors.Combinatorica, 44:467–507, 2024

Chun-Hung Liu. Defective coloring is perfect for minors.Combinatorica, 44:467–507, 2024

2024
[28]

PartitioningH-minor free graphs into three subgraphs with no large components.J

Chun-Hung Liu and Sang-il Oum . PartitioningH-minor free graphs into three subgraphs with no large components.J. Combin. Theory Ser. B, 128:114–133, 2018

2018
[29]

Chun-Hung Liu and David R. Wood . Clustered coloring of graphs excluding a subgraph and a minor. 2019, arXiv:1905.09495

2019 arXiv
[30]

Chun-Hung Liu and David R. Wood . Clustered graph coloring and layered treewidth. 2019, arXiv:1905.08969

2019
[31]

Chun-Hung Liu and David R. Wood . Clustered variants of Hajós’ conjecture.J. Combin. Theory Ser. B, 152:27–54, 2022

2022
[32]

Chun-Hung Liu and David R. Wood . Clustered coloring of graphs with bounded layered treewidth and bounded degree.European J. Combin., p. 103730, 2023

2023
[33]

Chun-Hung Liu and David R. Wood . Quasi-tree-partitions of graphs with an excluded subgraph. 2024, arXiv:2408.00983

2024
[34]

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

2017
[35]

Graphs on surfaces

Bojan Mohar and Carsten Thomassen . Graphs on surfaces. Johns Hopkins University Press, 2001

2001
[36]

Sergey Norin, Alex Scott, Paul Seymour, and David R. Wood . Clustered colouring in minor-closed classes.Combinatorica, 39(6):1387–1412, 2019

2019
[37]

Sergey Norin, Alex Scott, and David R. Wood . Clustered colouring of graph classes with bounded treedepth or pathwidth.Combin. Probab. Comput., 32:122–133, 2023

2023
[38]

Bruce A. Reed . Tree width and tangles: a new connectivity measure and some applications. In R. A. Bailey , ed.,Surveys in Combinatorics, vol. 241 ofLondon Math. Soc. Lecture Note Ser., pp. 87–162. Cambridge Univ. Press, 1997

1997
[39]

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

1997
[40]

Graph minors

Neil Robertson and Paul Seymour . Graph minors. III. Planar tree-width.J. Combin. Theory Ser. B, 36(1):49–64, 1984

1984
[41]

Graph minors

Neil Robertson and Paul Seymour . Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms, 7(3):309–322, 1986

1986
[42]

Graph minors

Neil Robertson and Paul Seymour . Graph minors. V. Excluding a planar graph.J. Combin. Theory Ser. B, 41(1):92–114, 1986

1986
[43]

Quickly excluding a planar graph

Neil Robertson, Paul Seymour, and Robin Thomas . Quickly excluding a planar graph. J. Combin. Theory Ser. B, 62(2):323–348, 1994

1994
[44]

Jan van den Heuvel and David R. Wood . Improper colourings inspired by Hadwiger’s conjecture. J. London Math. Soc., 98:129–148, 2018. arXiv:1704.06536

2018 arXiv
[45]

David R. Wood. Defective and clustered graph colouring.Electron. J. Combin., DS23, 2018. Version 1. 13

2018

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.

[1] [1]

A separator theorem for nonplanar graphs

Noga Alon, Paul Seymour, and Robin Thomas . A separator theorem for nonplanar graphs. J. Amer. Math. Soc., 3(4):801–808, 1990

1990

[2] [2]

Planar separators.SIAM J

Noga Alon, Paul Seymour, and Robin Thomas . Planar separators.SIAM J. Discrete Math., 7(2):184–193, 1994

work page 1994

[3] [3]

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

1989

[4] [4]

Drawing planar 3-trees with given face areas

Therese Biedl and Lesvia Elena Ruiz Velázquez . Drawing planar 3-trees with given face areas. Comput. Geom., 46(3):276–285, 2013

work page 2013

[5] [5]

Bodlaender

Hans L. Bodlaender . A partialk-arboretum of graphs with bounded treewidth.Theoret. Comput. Sci., 209(1-2):1–45, 1998

1998

[6] [6]

Marcin Briański, Robert Hickingbotham, and David R. Wood . Defective and clustered colouring of graphs with given girth. 2024, arXiv:2404.14940

work page arXiv 2024

[7] [7]

Weak diameter choosability of graphs with an excluded minor

Joshua Crouch and Chun-Hung Liu . Weak diameter choosability of graphs with an excluded minor. J. Combin. Theory Ser. B, 174:28–70, 2025

work page 2025

[8] [8]

Graph theory, vol

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

work page 2018