Clustered Variants of Haj\'os' Conjecture

Chun-Hung Liu; David R. Wood

REVIEW 2 major objections 3 minor 33 references

Clustered Variants of Haj\'os' Conjecture

T0 review · 2 major / 3 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read Every graph with no subdivision of $K_{s+1}$ is colorable with $4s-5$ colors and bounded monochromatic components.

desk verdict First O(s) clustered coloring bound for K_{s+1}-subdivision-free graphs, built on a clever transfer lemma whose omitted restricted version is the only real gap. read the letter →

arxiv 1908.05597 v4 pith:PIYI7MQU submitted 2019-08-14 math.CO cs.DM

Chun-Hung Liu , David R. Wood This is my paper · ORCID

classification math.COcs.DM MSC 05C1505C83

keywords Hajósconjectureclusteredcoloringgraphsubdivisionslistmonochromaticcomponentstreewidthminorstangles

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

The paper proves that Hajós' conjecture, though false in its original form, holds up to a constant factor once each color class is allowed to split into components of bounded size. Concretely, for every $s$ there is an integer $\eta$ such that every graph containing no subdivision of the complete graph $K_{s+1}$ admits a coloring with at most $4s-5$ colors in which every monochromatic component has at most $\eta$ vertices. This is the first $O(s)$ bound for these graphs, whereas the original conjecture fails because some such graphs need roughly $s^2/\log s$ colors when components must be single vertices. The same approach yields stronger results for bounded-treewidth graphs, for graphs with an excluded minor, and for graphs with an excluded subdivision of a bounded-degree graph, all with bounded clustering.

What carries the argument

The central objects are clustered colorings, in which every monochromatic component has bounded size, and almost $(\le 1)$-subdivisions, where at most one edge of the subdivided graph is subdivided more than once. The proof machinery is a list-coloring framework built around a distinguished set $Y_1$ of vertices whose lists have size one; a 'progress' operation moves vertices into $Y_1$ while pruning the lists of their neighbors. The deepest input is a tangle-based structure theorem for graphs excluding a fixed bounded-degree subdivision: any large tangle controlling a large clique minor forces a small exceptional set $Z$ such that every vertex outside $Z$ lies on the small side of a low-order separation. These tools split the graph into smaller pieces, color each piece by induction, and glue the colorings so that every monochromatic component stays bounded.

What would settle it

For some fixed $s$ and arbitrarily large $\eta$, construct a graph $G$ with no $K_{s+1}$-subdivision such that every coloring with at most $4s-5$ colors has a monochromatic component with more than $\eta$ vertices; such a graph would directly disprove Theorem 6, the paper's central claim.

Watch

Extended reading notes

Core claim

The central discovery is that the obstruction that kills Hajós' conjecture—the chromatic number of $K_{s+1}$-subdivision-free graphs can grow like $s^2/\log s$—disappears when monochromatic components are allowed to be large but bounded. The main theorem states that for each $s$ there exists $\eta$ such that every graph with no $K_{s+1}$-subdivision has a coloring with at most $\max\{4s-5,1\}$ colors and every monochromatic component has at most $\eta$ vertices. The proof proceeds through a stronger family of statements about graphs avoiding almost $(\le 1)$-subdivisions of $K_{s+1}$, using list-coloring with a distinguished set of precolored vertices and a structure theorem that confines large tangle structure to a small exceptional set. The final $O(s)$ bound is the first linear upper bound on the clustered chromatic number of $K_{s+1}$-subdivision-free graphs.

Load-bearing premise

The argument's load-bearing premise is that graphs excluding a fixed bounded-degree subdivision admit the tangle-based small-exception structure described in Theorem 14, together with an unproved companion lemma (Lemma 19); if either of those gives way, the linear bound no longer follows.

Editorial extensions

If this is right

The clustered form of Hajós' conjecture is settled up to a constant factor: $O(s)$ colors with bounded monochromatic components suffice for every $K_{s+1}$-subdivision-free graph.
In the bounded-treewidth case the number of colors is optimal: some treewidth-$(s-1)$ graphs need $s$ colors even with arbitrarily large allowed clustering, so Theorem 1 cannot be improved without extra assumptions.
Excluding a general minor instead of a subdivision costs exactly one extra color: every graph with no $H$-minor and no almost $(\le 1)$-subdivision of $K_{s+1}$ is $(s+1)$-colorable with bounded clustering.
For subdivision exclusion, the color count grows linearly with the maximum degree $d$ of the excluded graph: $\max\{s+3d-5,2\}$ colors suffice, and replacing the almost-subdivision prohibition by a $K_{s,t}$-subgraph prohibition gives $\max\{s+3d-4,2\}$.
The lower-bound construction shows the clustering number cannot be independent of $s$; it must grow at least like $\Omega(s/\log s)$ in the worst case.

Reading between the lines

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

A likely next step is to make the clustering bound explicit and small: all $\eta$ values in the theorems come from iterated functions and are not evaluated, so the theorem establishes existence but not practical colorings.
The method indicates that linear clustered colorings may extend to graphs excluding a subdivision of any fixed graph $H$, with constants depending only on $|V(H)|$ and $\Delta(H)$, not just to complete graphs; the almost-$(\le 1)$-subdivision statements are evidence that the decomposition is robust.
Testing the small case $s=4$ could sharpen the constant: if the $11$-color bound for $K_5$-subdivision-free graphs could be improved, the constant $4$ in $4s-5$ is not optimal, while a lower-bound example would identify the true linear rate.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

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

Theorem 6 is the headline and it holds up as far as I can see: the first O(s) clustered coloring bound for graphs excluding a K_{s+1}-subdivision, improving the earlier O(s^2) proper-coloring bounds and matching the lower bound up to a constant factor. The almost (≤1)-subdivision condition and faithful list assignments are genuinely useful strengthenings, and Theorems 1–5 are nontrivial consequences, not afterthoughts.

The paper is well-structured. Section 3's Lemma 16 is a long but mostly readable reduction from the Liu–Thomas structure theorem for excluded subdivisions. Section 4's Lemma 18 is the technical core, and its proof is detailed and coherent. I did not find a direct mathematical error.

The soft spots are what you'd expect from a paper at the frontier of its own series. Lemma 19, which transfers Lemma 18 to restricted list assignments, is stated with 'the proof is identical, so we omit it.' That is a real omission because Lemma 18's proof is long enough that 'identical' is not a trivial assertion. A referee should ask for the restricted proof or at least a clear statement of why each step survives the condition L(v)⊆[β+r]. The stress-test note about Claim 18.1 identifies a line that looks wrong on its face: the case |NG(v)∩Y1|>β' is actually vacuous for v∈V(C), since NG(v)∩Y1⊆P and |P|=s−1<β'. The printed chain is misleading, but the case being vacuous means it is harmless. A revision should fix that line.

The other caveat is that the proof leans heavily on Theorem 14 from Liu–Thomas and on Theorems 8–9 plus Lemmas 10–13 from the companion preprints [23,24]. These are not reproved here. That is acceptable in a series, but a referee needs to verify those imports. The self-citation has real content, not circularity.

Overall the central claim is likely correct. The bound is interesting, the framework is reusable, and the writing is careful. The paper deserves a serious referee; I would recommend acceptance after the authors supply Lemma 19's proof and clean up the vacuous case.

Referee Report

2 major / 3 minor

Summary. The paper proves several clustered-coloring results in the direction of Hajós' conjecture. It introduces the notion of an almost (≤1)-subdivision of a graph and shows, among other things, that graphs of bounded treewidth with no such subdivision of K_{s+1} are s-choosable with bounded clustering (Theorem 1), that graphs with no H-minor and no such subdivision are (s+1)-colorable with bounded clustering (Theorem 2), and that graphs with no K_{s+1}-subdivision are (4s−5)-colorable with bounded clustering (Theorem 6). The proof strategy combines the authors' earlier clustered-coloring results for K_{s,t}-free graphs with a structure theorem of Liu and Thomas for graphs excluding a bounded-degree subdivision. A long reduction (Lemma 16) establishes a restricted list-coloring statement for K_{s,t}-free graphs with no H-subdivision, and a transfer lemma (Lemmas 18 and 19) is used to pass from the K_{s,t}-free setting to the setting of graphs with no almost (≤1)-subdivision of K_{s+1}.

Significance. If correct, Theorem 6 gives the first O(s) bound on the clustered chromatic number of graphs with no K_{s+1}-subdivision, settling the clustered analogue of Hajós' conjecture up to a constant factor. Theorems 1 and 2 also give best-possible or near-best-possible numbers of colors in their settings. The paper is carefully structured, and the long proof of Lemma 16 is written in a self-contained manner. However, the central Theorem 6 depends on Lemma 19, whose proof is omitted, and on structure theorems and companion-paper results that are not reproduced here. The manuscript therefore currently leaves a load-bearing verification to the reader.

major comments (2)

[Section 4, Lemma 19] The proof of Lemma 19 is omitted with the sentence 'The proof is identical, so we omit it.' This is a load-bearing step: Theorem 20(3) invokes Lemma 19, Theorem 20(4) follows from Theorem 20(3) with H=K_{s+1}, and Theorem 6 is then read off from Theorem 20(4). The transfer from restricted list-coloring results for K_{s,t}-free graphs to restricted faithful list-coloring results for graphs with no almost (≤1)-subdivision of K_{s+1} requires checking that the constructions of L′ and L* in the proof of Lemma 18 preserve the restricted condition L(v)⊆[β′+r′], and that the cardinality identities such as |L(v)|=β′+r′−|N_G(v)∩Y1| remain valid in the restricted setting. Because the proof is absent, the central O(s) bound of Theorem 6 cannot currently be verified from the manuscript alone. Please include the full proof or a detailed appendix that goes through the restricted case line by line.
[Section 4, Claim 18.1 in Lemma 18] In the proof of Claim 18.1, for a vertex v∈V(C) with |N_G(v)∩Y1|>β′, the manuscript asserts |N_G(v)∩P| > |N_G(v)∩Y1|. This inequality is not justified and is in fact false in general. Because C is disjoint from Y1, any neighbor of v in Y1 must lie in P, so N_G(v)∩Y1⊆P and the case is vacuous: |P|=s−1<β′. The proof should state this vacuity explicitly. This is not a fatal error in Lemma 18 as written, but it is precisely the kind of step that the omitted 'identical' proof of Lemma 19 must handle, and the manuscript currently leaves that verification unperformed.

minor comments (3)

[Section 4, final paragraph] The sentence 'This together with Lemma 15 complete the proof of Theorems 1, 2, 4 and 6' is inaccurate. Lemma 15 concerns graphs of maximum degree at most 1 and is used for Theorem 5 when d=1; it does not address Theorems 1, 2, 4 and 6. Moreover, the case s=2 is not covered by Theorem 20, which assumes s>2, and is not discussed. These small cases follow from the fact that graphs with no almost (≤1)-subdivision of K3 are forests, but they should be stated explicitly.
[Introduction and Section 2.2] The proof relies on Theorem 14 from [22] and on Theorems 8 and 9 and Lemmas 10–13 from the companion papers [23,24], none of which are reproduced. Please add a sentence indicating the publication status of these references so that the reader knows whether the dependency is on published work or on preprints under review.
[Introduction, remark after Theorem 5] The remark that graphs of arbitrarily high girth and chromatic number show that excluding finitely many subgraphs cannot ensure an upper bound is stated too quickly; high girth alone does not forbid all subdivisions of K_{s+1}. Please clarify the intended argument or rephrase the remark.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: Theorem 6 follows by parameter substitution from Lemma 16, Lemma 19, and independent companion statements; flagged proof gaps are correctness risks, not circularity.

full rationale

The derivation of Theorem 6 is: Theorem 20(4) is obtained from Theorem 20(3) by taking H=K_{s+1}; Theorem 20(3) follows from Lemma 16 plus Lemma 19; Lemma 16 is proved in this paper using Theorem 14 ([22]) and companion results ([23,24]); Theorem 20(1)-(2) similarly apply Theorem 8/9 with Lemma 18/19. At no point is the target statement (an O(s) clustered-coloring bound for K_{s+1}-subdivision-free graphs) used as a hypothesis. The cited Theorem 14 is a structure theorem about separations in graphs with no bounded-degree subdivision, not a coloring theorem, and the cited results from [23,24] are parameter-free statements about K_{s,t}-free graphs and list-assignment progress whose assumptions do not include the target result. Thus Hard Rule 4 applies: these self-citations are independent support and do not constitute circularity. The manuscript itself flags one load-bearing gap: Lemma 19 is stated with 'The proof is identical, so we omit it,' and Lemma 18 contains a case (|N_G(v)∩Y1| > beta') that is vacuous when the neighbor set is contained in P with |P|=s-1<beta'; these are correctness/support concerns, not demonstrations that a prediction is equivalent to an input. There are no fitted parameters, no definitional identities equating the derived bound with an assumption, and no uniqueness theorem invoked to force a choice. Therefore the circularity score is 0.

Assumptions & free parameters 0 free parameters · 4 assumptions · 2 invented entities

No parameter fitting occurs; all constants are existential and no numerical values are assigned. The central results rest on previously established theorems imported as axioms: the companion clustering results of the authors [23,24] and the subdivision-exclusion structure theorem [22]. The paper introduces two definitional objects, almost (≤1)-subdivisions and faithful list assignments, which are mathematical definitions rather than empirical postulates.

assumptions (4)

domain assumption Companion clustering theorems: graphs with no K_{s,t} subgraph and bounded treewidth (Theorem 8) or with an excluded minor (Theorem 9) admit bounded cluster list colorings.
Stated in Section 2.2 as Theorem 8 and Theorem 9 from arXiv:1905.09495; the present proofs reduce to these without re-deriving them.
domain assumption Structure theorem for excluding bounded-degree subdivisions: if a tangle in a graph controls a K_{floor(3dh/2)}-minor and the graph excludes an H-subdivision, then all but at most ξ vertices are separated by bounded-order cuts.
Theorem 14 from [22], invoked in Lemma 16; load-bearing for Theorems 4-6.
standard math Standard tangle and separation machinery from Robertson-Seymour theory.
Definitions and lemmas in Sections 2.4 and 3 are treated as background.
standard math Standard graph theory definitions: treewidth, minors, subdivisions, tangles, list coloring, and choosability.
Used throughout Section 2 without proof.

invented entities (2)

almost (≤1)-subdivision of H
purpose: A graph obtained from H by subdividing edges so that at most one edge is subdivided more than once; used to state stronger Hajós-type clustered coloring results.
Definitional notion introduced in the abstract and Section 1; it does not claim empirical existence.
faithful (s,r,Y1)-list-assignment
purpose: A list condition that guarantees a chosen color can avoid neighbor singletons; central to transferring K_{s,t}-free results to almost-subdivision-free graphs in Lemma 18.
A proof device defined in Section 4; no independent falsifiable handle.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Clustered Variants of Haj\'os' Conjecture." pith.science (2026). https://pith.science/paper/PIYI7MQU

@misc{pith2026190805597,
  author       = {Pith},
  title        = {Pith review of: Clustered Variants of Haj\'os' Conjecture},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PIYI7MQU}},
  note         = {Machine review of arXiv:1908.05597}
}

abstract

Haj\'os conjectured that every graph containing no subdivision of the complete graph $K_{s+1}$ is properly $s$-colorable. This conjecture was disproved by Catlin. Indeed, the maximum chromatic number of such graphs is $\Omega(s^2/\log s)$. We prove that $O(s)$ colors are enough for a weakening of this conjecture that only requires every monochromatic component to have bounded size (so-called clustered coloring). Our approach leads to more results. Say that a graph is an almost $(\leq 1)$-subdivision of a graph $H$ if it can be obtained from $H$ by subdividing edges, where at most one edge is subdivided more than once. Note that every graph with no $H$-subdivision does not contain an almost $(\leq 1)$-subdivision of $H$. We prove the following (where $s \geq 2$): (1) Graphs of bounded treewidth and with no almost $(\leq 1)$-subdivision of $K_{s+1}$ are $s$-choosable with bounded clustering. (2) For every graph $H$, graphs with no $H$-minor and no almost $(\leq 1)$-subdivision of $K_{s+1}$ are $(s+1)$-colorable with bounded clustering. (3) For every graph $H$ of maximum degree at most $d$, graphs with no $H$-subdivision and no almost $(\leq 1)$-subdivision of $K_{s+1}$ are $\max\{s+3d-5,2\}$-colorable with bounded clustering. (4) For every graph $H$ of maximum degree $d$, graphs with no $K_{s,t}$ subgraph and no $H$-subdivision are $\max\{s+3d-4,2\}$-colorable with bounded clustering. (5) Graphs with no $K_{s+1}$-subdivision are $(4s-5)$-colorable with bounded clustering. The first result shows that the weakening of Haj\'{o}s' conjecture is true for graphs of bounded treewidth in a stronger sense; the final result is the first $O(s)$ bound on the clustered chromatic number of graphs with no $K_{s+1}$-subdivision.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

33 extracted references · 29 canonical work pages

[1]

Par- titioning into graphs with only small components

Noga Alon, Guoli Ding, Bogdan Oporowski, and Dirk Vertigan . Par- titioning into graphs with only small components. J. Combin. Theory Ser. B, 87(2):231–243, 2003

work page 2003
[2]

Proof of a conjecture of Mader, Erdős and Hajnal on topological complete subgraphs

Béla Bollobás and Andrew Thomason . Proof of a conjecture of Mader, Erdős and Hajnal on topological complete subgraphs. European J. Combin., 19(8):883–887, 1998

work page 1998
[3]

Paul A. Catlin. Ha´jos’ graph-coloring conjecture: variations and counterexam- ples. J. Combin. Theory Ser. B, 26:268–274, 1979. 25

work page 1979
[4]

Improper coloring of graphs on surfaces.J

Ilkyoo Choi and Louis Esperet . Improper coloring of graphs on surfaces.J. Graph Theory, 91(1):16–34, 2019

work page 2019
[5]

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

work page 1952
[6]

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

arXiv 2017
[7]

A relative of Hadwiger’s conjecture.SIAM J

Katherine Edw ards, 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

work page 2015
[8]

On the conjecture of Hajós.Combina- torica, 1(2):141–143, 1981

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

work page 1981

Show all 33 references

[9]

Graph theory and probability.Canad

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

1959
[10]

Colouring planar graphs with three colours and no large monochromatic components

Louis Esperet and Gwenaël Joret . Colouring planar graphs with three colours and no large monochromatic components. Combinatorics, Probability & Computing, 23(4):551–570, 2014

2014
[11]

Islands in graphs on surfaces.SIAM J

Louis Esperet and Pascal Ochem . Islands in graphs on surfaces.SIAM J. Discrete Math., 30(1):206–219, 2016

2016
[12]

Chromatic number, clique subdivisions, and the conjectures of Hajós and Erdős-Fajtlowicz.Combina- torica, 33(2):181–197, 2013

Jacob Fox, Choongbum Lee, and Benny Sudakov . Chromatic number, clique subdivisions, and the conjectures of Hajós and Erdős-Fajtlowicz.Combina- torica, 33(2):181–197, 2013

2013
[13]

Bounded size components—partitions and transversals

Penny Haxell, Tibor Szabó, and Gábor Tardos . Bounded size components—partitions and transversals. J. Combin. Theory Ser. B, 88(2):281– 297, 2003

2003
[14]

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

2019
[15]

Jan v an den Heuvel and Da vid R. Wood . Improper colourings inspired by Hadwiger’s conjecture.J. London Math. Soc., 98:129–148, 2018

2018
[16]

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

2019
[17]

A weakening of the odd Hadwiger’s conjecture.Com- bin

Ken-ichi Ka w arabayashi. A weakening of the odd Hadwiger’s conjecture.Com- bin. Probab. Comput., 17(6):815–821, 2008

2008
[18]

A relaxed Hadwiger’s conjec- ture for list colorings.J

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

2007
[19]

Topological cliques in graphs

János Komlós and Endre Szemerédi . Topological cliques in graphs. II.Com- bin. Probab. Comput., 5(1):79–90, 1996

1996
[20]

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
[21]

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

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

2018
[22]

Excludingsubdivisionsofboundeddegree graphs

Chun-Hung Liu and Robin Thomas. Excludingsubdivisionsofboundeddegree graphs. J. Combin. Theory Ser. B, 134:1–35, 2019. 26

2019
[23]

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

2019 arXiv
[24]

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

2019
[25]

Triangulations and the Hajós conjecture.Electron

Bojan Mohar. Triangulations and the Hajós conjecture.Electron. J. Combin., 12:N15, 2005

2005
[26]

Bojan Mohar, Bruce Reed, and Da vid R. Wood . Colourings with bounded monochromatic components in graphs of given circumference.Australas. J. Com- bin., 69(2):236–242, 2017

2017
[27]

Conquering graphs of bounded treewidth

Sergey Norin. Conquering graphs of bounded treewidth. 2015. Unpublished manuscript

2015
[28]

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

2019
[29]

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
[30]

Hadwiger’s conjecture

Paul Seymour . Hadwiger’s conjecture. In John Forbes Nash Jr. and Michael Th. Rassias , eds., Open Problems in Mathematics, pp. 417–437. Springer, 2015

2015
[31]

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

2005
[32]

Da vid R. Wood . Contractibility and the Hadwiger conjecture. European J. Combin., 31(8):2102–2109, 2010. arXiv:0811.2012

2010 arXiv
[33]

Da vid R. Wood. Defective and clustered graph colouring.Electron. J. Combin., DS23, 2018. Version 1. 27

2018

Pith tools

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

[1] [1]

Par- titioning into graphs with only small components

Noga Alon, Guoli Ding, Bogdan Oporowski, and Dirk Vertigan . Par- titioning into graphs with only small components. J. Combin. Theory Ser. B, 87(2):231–243, 2003

work page 2003

[2] [2]

Proof of a conjecture of Mader, Erdős and Hajnal on topological complete subgraphs

Béla Bollobás and Andrew Thomason . Proof of a conjecture of Mader, Erdős and Hajnal on topological complete subgraphs. European J. Combin., 19(8):883–887, 1998

work page 1998

[3] [3]

Paul A. Catlin. Ha´jos’ graph-coloring conjecture: variations and counterexam- ples. J. Combin. Theory Ser. B, 26:268–274, 1979. 25

work page 1979

[4] [4]

Improper coloring of graphs on surfaces.J

Ilkyoo Choi and Louis Esperet . Improper coloring of graphs on surfaces.J. Graph Theory, 91(1):16–34, 2019

work page 2019

[5] [5]

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

work page 1952

[6] [6]

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

arXiv 2017

[7] [7]

A relative of Hadwiger’s conjecture.SIAM J

Katherine Edw ards, 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

work page 2015

[8] [8]

On the conjecture of Hajós.Combina- torica, 1(2):141–143, 1981

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

work page 1981