Pith. sign in

REVIEW 2 major objections 4 minor 14 references

Complexity Classification of Colouring Problems with Parity Constraints

T0 review · 2 major / 4 minor · reviewed 2026-08-01 · deepseek-v4-flash

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

Pith's one-line read The paper claims a complete P-or-NP-complete classification for every parity-constrained q-colouring variant, with a single cell—∨⋆-colouring for q≥3—left open.

desk verdict Worth serious refereeing: a useful classification with two as-written gaps in the q≥3 hardness proofs that look repairable, not fatal. read the letter →

arxiv 2607.16879 v1 pith:E3HMSGWU submitted 2026-07-18 cs.DS math.CO

Rémy Belmonte , Juan Pablo Bravo , Noleen Köhler , Haiko Müller This is my paper · ORCID
classification cs.DSmath.CO MSC 05C1505C8568Q17
keywords graphcolouringparityconstraintsoddstrongdefectiveNP-completenessedge-colouringregulargraphs
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 tries to settle, for every pair of local parity constraints, whether the resulting q-colouring problem is easy or hard. It proposes a complete classification: with two colours, with three colours, and with four or more colours, every σ1σ2-q-colouring is either polynomial-time solvable or NP-complete, and the single unclassified case is ∨⋆-colouring for q≥3. A σ1σ2-q-colouring restricts, at each vertex, the number of neighbours of its own colour (by σ1) and the number of neighbours of each other colour (by σ2), where the symbols range over even, odd, positive even, odd-or-zero, unconstrained, zero, positive, at-most-one, and exactly-one. If the classification is right, the familiar problems of proper colouring, defective colouring, exact defective colouring, odd colouring, and strong odd colouring all become entries in one 10-by-10 table, and the remaining puzzle is why the one variant that allows a vertex to see zero or an odd number of its own colour resists classification.

What carries the argument

The central object is the σ1σ2-q-colouring: a q-colouring in which σ1 constrains |N(v) ∩ c^{-1}(c(v))| and σ2 constrains |N(v) ∩ c^{-1}(i)| for every other colour i, with the ten symbols encoding even, odd, even-and-positive, odd-or-zero, unconstrained, zero, positive, zero-or-one, and exactly one. The carrying mechanism is complexity transfer on regular graphs: on q-regular inputs many variants collapse to the same improper rainbow colouring, so a reduction from q-edge-colouring settles a whole block of cells at once; the proper rainbow case is handled by observing that a proper rainbow q-colouring is exactly a covering projection onto K_q. In the polynomial direction, the proofs encode the

What would settle it

Inspect the gadget in the proof for q≥4: the clique on x_1,...,x_q has the edge x_1x_2 subdivided by y_v and a pendant p_v attached to x_1, and one external edge at each x_i. Count degrees: x_1 has q+1 neighbours, but x_2,...,x_q have q neighbours. Try to construct a 1?- or ∨?-colouring of this gadget in which the external neighbours of x_2,...,x_q receive colours different from x_i, consistent with the gadget constraints; exhibiting such a colouring would break the reduction from q-edge-colouring and show the claimed NP-hardness proof is incomplete.

Watch

Extended reading notes

Core claim

On the paper's own terms, the discovery is a three-way dichotomy. For q=2, every σ1σ2-2-colouring problem is classified: a block of eight are polynomial via systems of linear equations over the binary field, and all the others are NP-complete. For q=3 and for every q≥4 the same dichotomy is claimed: polynomial or NP-complete, with the sole exception of ∨⋆-q-colouring for q≥3, whose status is left open. The hard cases are obtained by reductions from NAE3SAT, from proper q-colouring, from q-edge-colouring on q-regular graphs, and from known defective and odd colouring problems; a recurring mechanism is that many distinct constraint pairs coincide on regular graphs, so a single hardness constru

Load-bearing premise

The NP-hardness proof for 1?- and ∨?-colouring with q≥4 colours rests on the statement that every vertex x_i in the K_q-based gadget has degree q+1; the construction actually gives degree q+1 only to x_1, so the parity step that forces x_i's external neighbour to share its colour is unsupported for i≥2.

Editorial extensions

If this is right

  • For two colours, every parity variant is now placed: a block of eight are solvable by Gaussian elimination, and the remaining variants are NP-complete, including ∨⋆-2-colouring.
  • For three and four or more colours, the only cell left open is ∨⋆-q-colouring; if the tables are correct, the complexity of the whole field is closed apart from that single question.
  • The classification makes the known hardness of proper colouring, defective colouring, exact defective colouring, odd colouring, and strong odd colouring readable from one grid, and it pins the difficulty of each variant to classical proper-colouring or edge-colouring hardness.
  • Many NP-complete cells hold even for regular graphs of degree tied to the number of colours, so structural restrictions such as regularity do not create tractability except where the tables already say polynomial.

Reading between the lines

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

  • If the degree-counting step in the q≥4 gadget for 1?- and ∨?-colouring cannot be repaired, the two NP-complete cells for q≥4 should be regarded as open, and the dichotomy would be near-complete rather than complete.
  • The authors conjecture that every ∨⋆-colourable graph can be ∨⋆-coloured with three colours; a proof would turn the last open cell into a polynomial-time problem, while a four-colour-forcing example would sharpen the remaining hardness question.
  • The same gadget-based, constraints-coincide-on-regular-graphs method might be applied to other constraint alphabets—for example, requiring each neighbour count to be a fixed residue modulo m—and would likely yield a similarly complete grid.
  • The linear-equation technique for q=2 suggests a testable extension: write the analogous equations over GF(2) for the q≥3 polynomial cells currently proved only by monochromatic colourings, and see whether the easy cases are exactly those with a one-row equation system.
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.

Referee Report

2 major / 4 minor

Summary. The paper introduces a unified framework of σ1σ2-q-colourings, where the number of neighbours of a vertex having the same colour and the number of neighbours of each other colour are each constrained by one of nine local conditions (even, odd, zero, non-zero, at most one, exactly one, unrestricted, etc.). It claims a complete complexity dichotomy for q = 2, q = 3, and q ≥ 4 colours, with the single open case ∨⋆ for q ≥ 3. The main text gives NAE3SAT-based component reductions for many q = 2 cases, reductions from defective colouring, proper colouring, edge-colouring, and graph covering for q ≥ 3, and polynomial cases via explicit GF(2) linear systems. If correct, the classification subsumes proper, defective, exact defective, odd, and strong odd colouring as entries in a single table.

Significance. The framework is natural and the resulting classification is substantial: it identifies exactly one open cell and unifies several previously studied colouring problems. The polynomial-time cases are supported by clean, explicit linear systems over GF(2), and the reductions are mostly concrete and checkable. The main caveat is that the NP-hardness proofs for the 1? and ∨? cells in §4.2.5, which are needed for Tables 2 and 3, are not correct as written; the defects appear repairable, but until repaired the completeness claim for those cells is not established. The open ∨⋆ case is honestly flagged, and the paper is a useful contribution if the identified proofs are corrected.

major comments (2)
  1. [§4.2.5, Theorem 65 (q = 3)] The construction defines a triangle x_1^v, x_2^v, x_3^v with subdivided edges and one external edge per x_i^v, but never defines the pendant vertices p_i^v that are used in the forward colouring (cσ(p_i^v) = cσ(y_i^v) = c(x_i^v)) and in Figure 34. As written, each x_i^v has degree 3, not degree 4; the given forward colouring gives x_i^v two same-coloured neighbours (y_{i-1}^v and y_i^v) and one different-coloured external neighbour, which violates the 1? constraint. The reverse direction also relies on the false premise that x_i^v has degree 4. The proof appears repairable by explicitly adding a pendant p_i^v to each x_i^v and colouring it c(x_i^v), but as printed Theorem 65 does not establish NP-hardness of 1?/∨?-3-colouring, and the corresponding cells in Table 2 are unsupported.
  2. [§4.2.5, Theorem 66, Claim 67 and following] Claim 67 states that every x_i^v has degree q+1 and therefore at least three same-coloured neighbours. In the construction only x_1^v has degree q+1; for i ≥ 2, x_i^v has degree q (q−1 clique neighbours plus one external edge). Thus the proof of Claim 67 does not apply to i ≥ 2. This matters because the subsequent extraction of a q-edge-colouring uses the claim to force each external edge to be monochromatic. The intended conclusion can be recovered: by Claim 68, the q−1 clique neighbours of x_i^v have pairwise distinct colours, none equal to c(x_i^v), so they already contain every other colour exactly once; the external neighbour must therefore have colour c(x_i^v), otherwise some other colour would appear twice, violating the ?-constraint. For x_1 the same argument applied to y_v, p_v, and the external neighbour gives the same conclusion. Nevertheless, the text as printed contains a fa
minor comments (4)
  1. [Lemma 1] The statement says 'an stc satisfying Πtac'; this should be 'Πstc'.
  2. [Theorem 66, final paragraph] The sentence beginning 'Similarly, since v_i for i ≥ 2 has degree q...' appears to contain a typo: it should refer to cσ(x_i^v), not cσ(x_1^v).
  3. [§2 Preliminaries] The text says 'we denote the set of vertices of G by V(G) and the set of edges of G by V(G)'; the second should be E(G).
  4. [Theorem 65 / Figure 34] The theorem and figure mention pendant vertices p_i^v, but the construction does not define them. If the intended repair is to add pendants, the construction and figure must be made consistent.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: all reductions start from independent NP-complete problems and all polynomial cases are explicit GF(2) systems; the proof gaps noted by the reader are correctness issues, not circular reasoning.

full rationale

The paper's derivation chain is self-contained against external sources. Every NP-hardness result is obtained by a reduction from an established NP-complete problem (NAE3SAT, proper colouring, edge-colouring, defective colouring, or graph covering), and every polynomial-time result is proved by constructing an explicit system of linear equations over GF(2) and solving it by Gaussian elimination. The only self-citations are to Belmonte–Sau [4] for NP-completeness of 1*-colouring and to the same authors' technique in Section 3.3; these are external published results used as source problems or as methodological inspiration, not as the conclusion of the present derivation. No parameter is fitted to data and then renamed a prediction; no result is assumed from itself; the complexity classification tables merely compile independently proven entries. The as-written defects in Theorem 65 (undefined vertices p_i) and Theorem 66/Claim 67 (false degree premise for x_i^v, i>=2) are genuine correctness gaps in the printed proofs, but they are not circularity: the reductions still target independent problems and the intended arguments do not rely on the paper's own conclusions. Therefore the circularity burden is zero.

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

No numeric parameters are fitted; the paper is purely combinatorial. It relies on standard NP-completeness assumptions and on the correctness of the described gadget constructions, which in several places are only asserted with 'easy to verify' and missing figures. These gadget assertions, not numerical fitting, are the real evidential burden.

assumptions (5)
  • standard math NAE3SAT is NP-complete (used as the source problem for most Section 3.1 reductions).
    The reductions in Section 3.1 construct tacs and stcs and invoke Lemma 1, which assumes an NP-complete source problem. This is standard.
  • standard math Proper q-colouring is NP-complete for q≥3.
    Used in Theorem 39, 40, 41, 42, 43 as the base for reductions in Section 4.1.
  • standard math q-edge-colouring is NP-complete for q≥3, even on q-regular graphs.
    Used in Section 4.2 (Theorems 49, 53, 60, 62, 65, 66, 69, 74) as the source problem for several NP-hardness proofs.
  • standard math Defective q-colouring with defect 1 is NP-complete for q≥2.
    Used in Theorems 25 and 26 as the base for ?∨- and ?+-colouring reductions.
  • standard math H-cover is NP-complete for H=K_q with q≥4.
    Used in Theorem 58 to prove NP-completeness of proper rainbow q-colouring for q≥4 via graph covering.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Complexity Classification of Colouring Problems with Parity Constraints." pith.science (2026). https://pith.science/paper/E3HMSGWU

@misc{pith2026260716879,
  author       = {Pith},
  title        = {Pith review of: Complexity Classification of Colouring Problems with Parity Constraints},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/E3HMSGWU}},
  note         = {Machine review of arXiv:2607.16879}
}
abstract

We study variants of graph colouring with parity constraints. More specifically, we consider $q$-colourings $c\colon V(G)\rightarrow \{1,\dots,q\}$ of a graph $G$ where, for every vertex $v\in V(G)$, the number of neighbours $w$ of $v$ with $c(w)=c(v)$ is restricted to be odd, even, positive, zero or a combination thereof. For every colour $i\neq c(v)$ the number of neighbours $w$ of $v$ with $c(w)=i$ is restricted by a constraint of similar type. Many known colouring problems such as proper colouring, defective colouring, exact defective colouring, odd colouring, and strong odd colouring can be described within this framework of constraining graph colourings, and therefore considering variants constitutes a natural generalisation of known colouring problems. We provide a comprehensive study of the computational complexity of different combinations of constraints involving parity.

Figures

Figures reproduced from arXiv: 2607.16879 by the authors.

Figure 10
Figure 10. Using Claim 12 it is easy to verify that the tac has precisely two [PITH_FULL_IMAGE:figures/full_fig_p013_10.png] view at source ↗
Figure 21
Figure 21. True is encoded by the two vertices of an outlet having the same colour and their [PITH_FULL_IMAGE:figures/full_fig_p019_21.png] view at source ↗
Figure 25
Figure 25. Construction for q ≥ 2. First, let c : V (G) → [q] be a 1!-colouring of G. We obtain a 0!-colouring c0! : V (H) → [q] of H as follows. Fix a vertex v ∈ V (G). For each α ∈ {1, 2}, we set c0!(v α) = c0!(x v q ) = c(v). Let c1, . . . , cq−1 be the remaining colours (the colours different from c(v)). We assign x v i the colour ci for each i ∈ [q − 1]. It is easy to verify that c0! is a 0!-colouring, as illustrated in … view at source ↗
Figures from the paper (2 more)
Figure 27
Figure 27. Figure 27: Gadget representing a vertex v of degree 3 of G in H for 3 colours. First, let c : V (G) → [q] be a proper colouring of G. We obtain a 0?-colouring c0? : V (H) → [q] of H as follows. For each v ∈ V (G) and i ∈ [p], we set c0?(x v i ) = c(v). It is easy to verify that …
Figure 34
Figure 34. Figure 34: Gadget representing vertex v of G in H, showing the triangle, the subdivision vertices, and the pendants. each vertex v ∈ V (G) and for each i ∈ [3], we set cσ(p v i ) = cσ(y v i ) = c(x v i ). It is easy to verify that cσ is a σ-colouring, as illustrated in [PITH_FU…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

14 extracted references · 5 canonical work pages

  1. [7]

    URL: https://doi.org/10.1007/s00224-025-10221-2, doi: 10.1007/S00224-025-10221-2. 12 J. E. Dunbar, S. M. Hedetniemi, S. T. Hedetniemi, D. P. Jacobs, J. Knisely, R. C. Laskar, and D. F. Rall. Fall colorings of graphs.J. Combin. Math. Combin. Comput., 33:257–273,

    work page doi:10.1007/s00224-025-10221-2

  2. [10]

    Strong odd coloring of sparse graphs.arXiv preprint arXiv:2401.11653,

    21 Hyemin Kwon and Boram Park. Strong odd coloring of sparse graphs.arXiv preprint arXiv:2401.11653,

    arXiv

  3. [13]

    Colorings with neighborhood parity condition

    URL:https://arxiv.org/abs/2112.13710,doi:10.48550/ARXIV.2112.13710. 27 Michał Pilipczuk. Strong odd colorings in graph classes of bounded expansion.Electron. J. Comb., 32(4), 2025.doi:10.37236/14259. 28 Thomas J. Schaefer. The complexity of satisfiability problems. InProceedings of the Tenth Annual ACM Symposium on Theory of Computing, STOC ’78, page 216–...

    work page Pith review arXiv doi:10.48550/arxiv.2112.13710 2025

  4. [1973]

    10 LenoreCowen, WayneGoddard, andC.EstherJesurum

    doi:10.1016/0012-365X(73)90138-6. 10 LenoreCowen, WayneGoddard, andC.EstherJesurum. Defectivecoloringrevisited.Journal of Graph Theory, 24(3):205–219,

    work page doi:10.1016/0012-365x(73)90138-6

  5. [1978]

    29 Alex D

    Association for Computing Machinery.doi:10.1145/800133.804350. 29 Alex D. Scott. On induced subgraphs with all degrees odd.Graphs Comb., 17(3):539–553, 2001.doi:10.1007/s003730170028. 30D.R. Woodall. Improper colourings of graphs.Graph colourings, 218:45–63,

    arXiv 2001

  6. [1981]

    doi:10.1137/0210055. R. Belmonte, J.P. Bravo, N. Köhler and H. Müller 23:49 17 Robert W. Irving and David F. Manlove. The b-chromatic number of a graph.Discrete Applied Mathematics, 91(1):127–141,

    doi:10.1137/0210055

  7. [1997]

    URL:https://onlinelibrary.wiley.com/doi/abs/10. 1002/%28SICI%291097-0118%28199703%2924%3A3%3C205%3A%3AAID-JGT2%3E3.0.CO%3B2-T, arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.1002/\%28SICI\%291097-0118\ %28199703\%2924\%3A3\%3C205\%3A\%3AAID-JGT2\%3E3.0.CO\%3B2-T, doi:10.1002/(SICI) 1097-0118(199703)24:3<205::AID-JGT2>3.0.CO;2-T. 11 Erik D. Demaine, Krit...

    doi:10.1002/(sici

  8. [1999]

    18 Richard M

    URL:https://www.sciencedirect.com/science/ article/pii/S0166218X98001462,doi:10.1016/S0166-218X(98)00146-2. 18 Richard M. Karp.Reducibility Among Combinatorial Problems, pages 219–241. Springer Berlin Heidelberg, Berlin, Heidelberg, 2010.doi:10.1007/978-3-540-68279-0_8. 19 Jan Kratochvíl, Andrzej Proskurowski, and Jan Arne Telle. Complexity of graph cover...

    work page doi:10.1016/s0166-218x(98)00146-2 2010

Show all 14 references
  1. [2012]

    26 Mirko Petrusevski and Riste Skrekovski

    URL: https://arxiv.org/abs/1201.2852,arXiv:1201.2852. 26 Mirko Petrusevski and Riste Skrekovski. Colorings with neighborhood parity condition,

    arXiv

  2. [2013]

    9 Vašek Chvátal

    doi:10.1137/120880471. 9 Vašek Chvátal. Tough graphs and hamiltonian circuits.Discret. Math., 5(3):215–228,

    doi

  3. [2021]

    5 Jan Bok, Jiří Fiala, Nikola Jedličková, Jan Kratochvíl, and Paweł Rzążewski

    doi:10.1007/s00453-021-00830-x. 5 Jan Bok, Jiří Fiala, Nikola Jedličková, Jan Kratochvíl, and Paweł Rzążewski. List covering of regular multigraphs with semi-edges.Algorithmica, 86(3):782–807,

    doi

  4. [2024]

    NP-completeness of finding the chromatic index of regular graphs

    22 Daniel Leven and Zvi Galil. NP-completeness of finding the chromatic index of regular graphs. J. Algorithms, 4(1):35–44, 1983.doi:10.1016/0196-6774(83)90032-9. 23László Lovász.Combinatorial Problems and Exercises. North-Holland,

    1983 doi

  5. [2025]

    2025.114601,doi:10.1016/J.DISC.2025.114601

    URL: https://doi.org/10.1016/j.disc. 2025.114601,doi:10.1016/J.DISC.2025.114601. 8 Panagiotis Cheilaris, Balázs Keszegh, and Dömötör Pálvölgyi. Unique-maximum and conflict- free coloring for hypergraphs and tree graphs.SIAM J. Discret. Math., 27(4):1775–1787,

    2025

  6. [2026]

    2 Jungho Ahn, Seonghyuk Im, and Sang-il Oum

    URL: https://arxiv.org/abs/2603.26214,arXiv:2603.26214. 2 Jungho Ahn, Seonghyuk Im, and Sang-il Oum. The proper conflict-free k-coloring problem and the odd k-coloring problem are NP-complete on bipartite graphs.Discrete Applied Mathematics, 377:10–17,

    arXiv

Pith tools

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