Strong odd colorings in graph classes of bounded expansion

Micha{\l} Pilipczuk

REVIEW 1 major objections 5 minor 16 references

Strong odd colorings in graph classes of bounded expansion

T0 review · 1 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read Bounded-expansion graph classes get constant strong odd colorings

desk verdict Strong new result, but Lemma 4.1 is false as stated and the proof of Theorem 1.3 needs repair. read the letter →

arxiv 2505.15288 v1 pith:NI4CALLZ submitted 2025-05-21 math.CO cs.DM

Micha{l} Pilipczuk This is my paper

classification math.COcs.DM MSC 05C15

keywords strongoddcoloringboundedexpansionsetsystemssemi-ladderindex2VCdimensionsubchromaticnumbergraphsparsegraphs

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 every graph class of bounded expansion admits a proper coloring with a constant number of colors such that, for any fixed radius $d$, every ball of radius $d$ contains every color either zero times or an odd number of times. This resolves, for $d=1$, an open question about the strong odd chromatic number on bounded-expansion classes, which include planar graphs and all proper minor-closed classes. The proof reduces the graph problem to a set-system problem: the strong odd coloring number of a set system is bounded by a function of its semi-ladder index, its 2VC dimension, and the maximum subchromatic number of its induced subsystems. Because ball systems of bounded-expansion graphs have all three parameters bounded, the graph result follows.

What carries the argument

The load-bearing object is the semi-ladder index of a set system: the largest length of a sequence of elements $u_1,\dots,u_\ell$ and sets $F_1,\dots,F_\ell$ such that $u_i \notin F_i$ but $u_i \in F_j$ for every $j>i$. The proof shows that when a set system has bounded semi-ladder index, bounded 2VC dimension, and bounded subchromatic number, one can partition its universe into cliques of its Gaifman graph (clusters) so that each cluster has a strictly smaller semi-ladder index; this is Lemma 4.1. The partition uses a known covering theorem (Theorem 2.3) which, under bounded 2VC dimension and no large independent set in the Gaifman graph, covers the universe with few sets. A second supporting ingredient is Theorem 3.3, which establishes that the hereditary closure of ball systems of a bounded-expansion graph class has bounded subchromatic number; this is proved by showing the class is transducible from the original class, excludes some large complete bipartite induced subgraph, and then invoking low shrubdepth colorings to bound the subchromatic number.

What would settle it

Construct a family of set systems in which some element belongs to no set, while semi-ladder index, 2VC dimension, and the maximum subchromatic number of induced subsystems stay bounded, but the strong odd chromatic number grows without bound; such a family would refute Theorem 1.3 as stated and show the missing coverability hypothesis is essential.

Watch

Extended reading notes

Core claim

The paper's central claim is Theorem 1.2: for every fixed $d$ and every graph class $\mathscr{C}$ of bounded expansion, there is a constant $c$ such that every graph $G$ in $\mathscr{C}$ can be properly colored with at most $c$ colors in a way that every radius-$d$ ball contains each color an odd number of times or not at all. The $d=1$ case, Theorem 1.1, states that the strong odd chromatic number of any such class is bounded, answering a question raised in a recent paper. The heart of the argument is a set-system statement, Theorem 1.3: if a set system has bounded semi-ladder index, bounded 2VC dimension, and every induced subsystem has bounded subchromatic number, then the whole system has a bounded strong odd coloring number. The proof of the set-system theorem proceeds by induction on the semi-ladder index, splitting the universe into clusters whose induced subsystems have strictly smaller semi-ladder index, and then recursively coloring each cluster.

Load-bearing premise

The proof assumes, without stating it, that every element of every set system lies in at least one set of the family; the central induction step can break for elements that belong to no set.

Editorial extensions

If this is right

For $d=1$, this gives a uniform bound on the strong odd chromatic number of every bounded-expansion class, settling the open question.
The result holds for every fixed radius $d$: the same constant palette works for all radius-$d$ balls, not just closed neighborhoods.
The author notes that the argument extends without essential change to a modulus variant: every color may be required to appear zero times or $1 \pmod m$ times in every ball, for any fixed $m$.
Since every proper minor-closed class has bounded expansion, the result recovers and generalizes the known boundedness of strong odd chromatic numbers on planar graphs and other minor-closed classes.
Theorem 1.3 isolates a set-system condition that suffices for bounded strong odd coloring, which the author suggests could anchor a characterization of hereditary set-system classes with this property.

Reading between the lines

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

The proof of Lemma 4.1 uses a covering theorem that assumes every element belongs to at least one set; the paper does not state this hypothesis, and without it the claimed strict drop in semi-ladder index can fail, as when an element sits in no set. The graph-level result still holds because every vertex lies in its own ball, but Theorem 1.3 may need the coverability condition added.
A direct test of Theorem 1.3: search for a hereditary family of set systems with bounded semi-ladder index, 2VC dimension, and induced subchromatic number but unbounded strong odd chromatic number under failing coverability; such a family would pinpoint the true scope of the theorem.
The subchromatic bound for hereditary closures of ball systems is obtained through first-order transductions and low shrubdepth colorings; a purely combinatorial proof could give explicit (and presumably smaller) constants, which would matter for algorithmic coloring of sparse graphs.
The modulus-$m$ extension suggests that the 'zero or odd' condition is one instance of a family of conditions parametrized by a modulus; the same induction might apply to other modular constraints, connecting to conflict-free and odd coloring themes.

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

First, the punchline: this paper very likely proves the right theorem, but as written the proof has a real hole. Theorem 1.2 (and hence Theorem 1.1) answers the Goetze et al. question for bounded expansion, with a clean radius-d generalization. The set-system framework — bounding strong odd chromatic number by semi-ladder index, 2VC dimension, and hereditary subchromatic number — is a genuinely useful way to organize the argument. The Section 3 proof that the hereditary closure of ball systems has bounded subchromatic number, via transductions and low shrubdepth colorings, is well executed and is a contribution in its own right.

The problem is Lemma 4.1. It is false as stated. Take U={a,b,c}, F={{a,b}}. The hypotheses hold: 2VC dimension is 2, the Gaifman graph is a clique plus an isolated vertex so the subchromatic number is 1, and U is not in F. But any subcoloring gives a component {c}, and S[{c},F] has family {∅}, which still has semi-ladder index 1, so the required strict decrease fails. The proof applies Theorem 2.3 to each cluster Y to cover Y by sets from F, and Theorem 2.3 needs the family to cover the universe. That is not stated in Lemma 4.1. Moreover, simply adding a coverability hypothesis to Lemma 4.1 and Theorem 1.3 is not obviously enough: in the induction step of Theorem 1.3, the argument removes U from F, and that can break coverability. So the gap is load-bearing, not a typo.

That said, the central theorem is very likely true. The ball systems used in the application are coverable, and the graph-level derivation from Theorem 1.3 to Theorem 1.2 is sound. A careful revision that either restricts the set-system theorem to coverable systems and keeps the induction inside that class, or treats uncovered elements separately, should go through. The citations look honest; the heavy use of related work from the same group is justified because those are the right tools.

Bottom line: a significant result with a solid architecture and a repairable but real flaw. I'd send it to a good referee, not desk reject, but the referee should be asked to check Lemma 4.1 and the induction carefully before acceptance.

Referee Report

1 major / 5 minor

Summary. The paper proves that every graph class of bounded expansion admits, for each fixed d, a proper coloring with a bounded number of colors in which every radius-d ball contains each color either zero times or an odd number of times. For d=1 this answers a question of Goetze et al. about the boundedness of the strong odd chromatic number in bounded-expansion classes. The proof is set-system-theoretic: it introduces a general theorem (Theorem 1.3) bounding the strong odd chromatic number of a set system in terms of its semi-ladder index, 2VC dimension, and the maximum subchromatic number of induced subsystems, and then verifies these parameters for radius-d ball systems using known results on semi-ladder index, 2VC dimension, and a new transduction-based proof of bounded subchromatic number for the hereditary closure of ball systems.

Significance. If the proof is made fully sound, the main theorem is a substantial and natural extension of the recent positive result for minor-closed classes to all bounded-expansion classes, and it answers an explicitly posed question. The set-system framework and the strengthening of the subchromatic-number result via first-order transductions are interesting and likely reusable. The paper is honest about the limits of its tools, and the main result is clearly stated and would be falsifiable in principle. The proof is modular and mostly well organized, but one load-bearing lemma is currently false as stated; the gap is local and repairable for the main application.

major comments (1)

[Lemma 4.1] Lemma 4.1 is false as stated because its proof applies Theorem 2.3 to S[Y,F] without verifying the hypothesis that the union of the family equals the universe. For the induced subsystem S[Y,F] this hypothesis is exactly that every y in Y belongs to some F in F, but the lemma only assumes U notin F, which does not imply this. A concrete counterexample is S = ({a,b,c}, {{a,b}}): its 2VC dimension is 2 (the pair {a,b} is 2-shattered), its subchromatic number is 1 (the Gaifman graph is an edge plus an isolated vertex), and U notin F, yet the component {c} of Gaif(S) yields S[{c},F] = ({c}, {empty set}), whose semi-ladder index is 1, equal to the semi-ladder index of S. Thus the strict decrease asserted in Claim 4.2 fails, and the induction in Theorem 1.3 is not justified as written. The gap is repairable for the main application because in Balls_d(G) every vertex lies in its own ball, so the relevant systems are coverable; the authors should add a coverability hypothesis to Lemma 4.1 and Theorem 1.3, or otherwise handle vertices that lie in no set of the family.

minor comments (5)

[Theorem 1.3, induction step] The partition of X_{i,T} is undefined when |X_{i,T}| = 0: the 'otherwise' case asks for a partition into two odd-size subsets, which does not exist for the empty family. The construction should set both parts empty when |X_{i,T}| = 0 and split into two odd parts only for even positive size; this is consistent with the later assertion that each part has size zero or odd.
[Lemma 3.12] In the proof of Lemma 3.12, 'there are d, m in D' should read 'there are d, m in N'; the symbols d and m denote numbers, not members of the graph class D.
[Theorem 3.13] In the statement of Theorem 3.13 and its use in the proof of Theorem 3.4, the variable name for a graph in the class is inconsistent: the theorem says 'for every graph G in C', but should say 'G in D' (or the class should be renamed consistently).
[Theorem 1.3, final verification] In the paragraph verifying that sigma is a totally strong odd coloring, the notation 'S X_{i,X}^a' and 'X_{i,X}^a' should be 'X_{i,T}^a' and 'S X_{i,T}^a'; the current notation is garbled and difficult to follow.
[Section 4] It would help the reader if the paper explicitly noted that Balls_d(G) is coverable, since that is precisely the property that makes the repaired Lemma 4.1 applicable to the main theorem.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the derivation is self-contained against external structural results. A missing coverability hypothesis in Lemma 4.1 is a correctness gap, not a circular step.

full rationale

Walking the derivation chain: Theorem 1.2 is obtained by applying Theorem 1.3 to Balls_d(G), after establishing bounded semi-ladder index (Lemma 2.4 via Fabia\'nski et al.), bounded 2VC dimension (Lemma 2.5 via Pilipczuk\u2013Siebertz), bounded subchromatic number of the hereditary closure (Theorem 3.3, proved here), and bounded chromatic number of C. Theorem 1.3 is proved by induction on the semi-ladder index using Lemma 4.1. None of these steps defines the target quantity in terms of itself, fits a parameter to the target, or renames a known result. The citations to prior work involving the author (e.g., [4], [5], [13], [16]) supply external theorems about semi-ladder index, 2VC dimension, low shrubdepth colorings, and powers; none assumes or contains the strong odd coloring theorem. The main non-circularity concern is a genuine correctness gap in Lemma 4.1: the application of Theorem 2.3 to S[Y,F] requires that the family cover the universe, but the lemma only assumes U \notin F. If an element lies in no set, the family need not cover Y, so the subfamily Q_Y may not exist and Lemma 4.1 is false as stated (e.g., S=({a,b,c},{{a,b}})). This is an omitted hypothesis, not circular use of the conclusion; the main application Balls_d(G) is coverable, so the theorem is likely repairable. Because no derivation reduces to its own input, the circularity score is 0.

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

The graph-theoretic result relies on several deep external theorems (Ding-Seymour-Winkler, low shrubdepth colorings, monadic dependence of nowhere dense classes, semi-ladder and 2VC bounds for ball systems) and on an unstated coverability condition in Lemma 4.1. No numerical parameters are fitted and no new entities are postulated.

assumptions (4)

standard math Theorem 2.3 (Ding-Seymour-Winkler): a set system of 2VC dimension h whose Gaifman graph has no independent set larger than k can be covered by f(h,k) sets.
Used in Lemma 4.1 to cover each cluster by few sets; accepted external result from [3].
standard math Theorem 3.13 (Gajarsky et al.): classes of structurally bounded expansion admit low shrubdepth colorings.
Used in the proof of Theorem 3.4 to reduce the subchromatic number question to bounded shrubdepth classes; external result from [5].
standard math Nowhere dense classes are monadically dependent and rook graphs are not monadically dependent.
Used in Claim 3.6 to derive a contradiction from arbitrarily large induced K_{t,t} in the Gaifman class D.
ad hoc to paper Coverability of set systems: every element of the universe belongs to at least one set in the family.
Required to apply Theorem 2.3 to S[Y,F] and to prove Claim 4.2. Not stated in Lemma 4.1 or Theorem 1.3 and false for general set systems, e.g. U={a,b,c}, F={{a,b}}.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Strong odd colorings in graph classes of bounded expansion." pith.science (2026). https://pith.science/paper/NI4CALLZ

@misc{pith2026250515288,
  author       = {Pith},
  title        = {Pith review of: Strong odd colorings in graph classes of bounded expansion},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NI4CALLZ}},
  note         = {Machine review of arXiv:2505.15288}
}

abstract

We prove that for every $d\in \mathbb{N}$ and a graph class of bounded expansion $\mathscr{C}$, there exists some $c\in \mathbb{N}$ so that every graph from $\mathscr{C}$ admits a proper coloring with at most $c$ colors satisfying the following condition: in every ball of radius $d$, every color appears either zero times or an odd number of times. For $d=1$, this provides a positive answer to a question raised by Goetze, Klute, Knauer, Parada, Pe\~na, and Ueckerdt [ArXiv 2505.02736] about the boundedness of the strong odd chromatic number in graph classes of bounded expansion. The key technical ingredient towards the result is a proof that the strong odd coloring number of a sets system can be bounded in terms of its semi-ladder index, 2VC dimension, and the maximum subchromatic number among induced subsystems.

Figures

Figures reproduced from arXiv: 2505.15288 by the authors.

**Figure 1.** A semi-ladder of order 4, a comatching of order 4, a ladder of order 4, and a 2-shattered set of size 4. Solid edges represent membership, dashed gray edges represent non-membership, lack of an edge represents no specification. Naturally, for a graph class C , we may define the corresponding classes of set systems: Ballsd(C ) := {Ballsd(G): G ∈ C }. It turns out that provided d is fixed and C has bounded expansion, … view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

16 extracted references · 11 canonical work pages

[1]

Interpreting nowhere dense graph classes as a classical notion of model theory

Hans Adler and Isolde Adler. Interpreting nowhere dense graph classes as a classical notion of model theory. European Journal of Combinatorics , 36:322–330, 2014

work page 2014
[2]

On strong odd colorings of graphs

Yair Caro, Mirko Petru ˇsevski, Riste ˇSkrekovski, and Zsolt Tuza. On strong odd colorings of graphs. ArXiv preprint, abs/2410.02336, 2024

work page Pith review arXiv 2024
[3]

Seymour, and Peter Winkler

Guoli Ding, Paul D. Seymour, and Peter Winkler. Bounding the vertex cover number of a hypergraph. Combinatorica, 14(1):23–34, 1994

work page 1994
[4]

Progressive al- gorithms for domination and independence

Grzegorz Fabia ´nski, Michał Pilipczuk, Sebastian Siebertz, and Szymon Toru ´nczyk. Progressive al- gorithms for domination and independence. In Rolf Niedermeier and Christophe Paul, editors, 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, volume 126 ofLIPIcs, pages 27:1–27:16. Schloss Dagstuhl — Leibniz-Zentrum f¨ur I...

work page 2019
[5]

First-order interpretations of bounded expansion classes

Jakub Gajarsk ´y, Stephan Kreutzer, Jaroslav Ne ˇsetˇril, Patrice Ossona de Mendez, Michał Pilipczuk, Sebastian Siebertz, and Szymon Toru´nczyk. First-order interpretations of bounded expansion classes. ACM Transactions on Computational Logic , 21(4):29:1–29:41, 2020

2020
[6]

Shrub- depth: Capturing height of dense graphs

Robert Ganian, Petr Hlin ˇen´y, Jaroslav Neˇsetˇril, Jan Obdrˇz´alek, and Patrice Ossona de Mendez. Shrub- depth: Capturing height of dense graphs. Logical Methods in Computer Science , 15(1), 2019

2019
[7]

Strong odd coloring in minor-closed classes

Miriam Goetze, Fabian Klute, Kolja Knauer, Irene Parada, Juan Pablo Pe ˜na, and Torsten Ueckerdt. Strong odd coloring in minor-closed classes. ArXiv preprint, abs/2505.02736, 2025

work page Pith review arXiv 2025
[8]

Odd colourings, conflict-free colourings and strong colouring numbers

Robert Hickingbotham. Odd colourings, conflict-free colourings and strong colouring numbers. Aus- tralasian Journal of Combinatorics , 87:160–164, 2023

work page 2023

Show all 16 references

[9]

Strong odd coloring of sparse graphs.ArXiv preprint, abs/2401.11653, 2024

Hyemin Kwon and Boram Park. Strong odd coloring of sparse graphs.ArXiv preprint, abs/2401.11653, 2024

2024 arXiv
[10]

Proper conflict-free list-coloring, odd minors, subdivisions, and layered treewidth

Chun-Hung Liu. Proper conflict-free list-coloring, odd minors, subdivisions, and layered treewidth. Discrete Mathematics, 347(1):113668, 2024

2024
[11]

On nowhere dense graphs

Jaroslav Ne ˇsetˇril and Patrice Ossona de Mendez. On nowhere dense graphs. European Journal of Combinatorics, 32(4):600–617, 2011. 12

2011
[12]

Sparsity — Graphs, Structures, and Algorithms , vol- ume 28 of Algorithms and combinatorics

Jaroslav Ne ˇsetˇril and Patrice Ossona de Mendez. Sparsity — Graphs, Structures, and Algorithms , vol- ume 28 of Algorithms and combinatorics. Springer, 2012

2012
[13]

Clustering powers of sparse graphs

Jaroslav Ne ˇsetˇril, Patrice Ossona de Mendez, Michał Pilipczuk, and Xuding Zhu. Clustering powers of sparse graphs. Electronic Journal of Combinatorics , 27(4):4, 2020

2020
[14]

Sparsity

Marcin Pilipczuk, Michał Pilipczuk, and Sebastian Siebertz. Lecture notes for the course “Sparsity” given at Faculty of Mathematics, Informatics, and Mechanics of the University of Warsaw, Winter semesters 2017/18 and 2019/20. Available online at https://www.mimuw.edu.pl/ mp24...

2017
[15]

Graph classes through the lens of logic

Michał Pilipczuk. Graph classes through the lens of logic. ArXiv preprint, abs/2501.04166, 2025

2025 arXiv
[16]

Kernelization and approximation of distance-r independent sets on nowhere dense graphs

Michał Pilipczuk and Sebastian Siebertz. Kernelization and approximation of distance-r independent sets on nowhere dense graphs. European Journal on Combinatorics , 94:103309, 2021. 13

2021

Pith tools

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

[1] [1]

Interpreting nowhere dense graph classes as a classical notion of model theory

Hans Adler and Isolde Adler. Interpreting nowhere dense graph classes as a classical notion of model theory. European Journal of Combinatorics , 36:322–330, 2014

work page 2014

[2] [2]

On strong odd colorings of graphs

Yair Caro, Mirko Petru ˇsevski, Riste ˇSkrekovski, and Zsolt Tuza. On strong odd colorings of graphs. ArXiv preprint, abs/2410.02336, 2024

work page Pith review arXiv 2024

[3] [3]

Seymour, and Peter Winkler

Guoli Ding, Paul D. Seymour, and Peter Winkler. Bounding the vertex cover number of a hypergraph. Combinatorica, 14(1):23–34, 1994

work page 1994

[4] [4]

Progressive al- gorithms for domination and independence

Grzegorz Fabia ´nski, Michał Pilipczuk, Sebastian Siebertz, and Szymon Toru ´nczyk. Progressive al- gorithms for domination and independence. In Rolf Niedermeier and Christophe Paul, editors, 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, volume 126 ofLIPIcs, pages 27:1–27:16. Schloss Dagstuhl — Leibniz-Zentrum f¨ur I...

work page 2019

[5] [5]

First-order interpretations of bounded expansion classes

Jakub Gajarsk ´y, Stephan Kreutzer, Jaroslav Ne ˇsetˇril, Patrice Ossona de Mendez, Michał Pilipczuk, Sebastian Siebertz, and Szymon Toru´nczyk. First-order interpretations of bounded expansion classes. ACM Transactions on Computational Logic , 21(4):29:1–29:41, 2020

2020

[6] [6]

Shrub- depth: Capturing height of dense graphs

Robert Ganian, Petr Hlin ˇen´y, Jaroslav Neˇsetˇril, Jan Obdrˇz´alek, and Patrice Ossona de Mendez. Shrub- depth: Capturing height of dense graphs. Logical Methods in Computer Science , 15(1), 2019

2019

[7] [7]

Strong odd coloring in minor-closed classes

Miriam Goetze, Fabian Klute, Kolja Knauer, Irene Parada, Juan Pablo Pe ˜na, and Torsten Ueckerdt. Strong odd coloring in minor-closed classes. ArXiv preprint, abs/2505.02736, 2025

work page Pith review arXiv 2025

[8] [8]

Odd colourings, conflict-free colourings and strong colouring numbers

Robert Hickingbotham. Odd colourings, conflict-free colourings and strong colouring numbers. Aus- tralasian Journal of Combinatorics , 87:160–164, 2023

work page 2023