{"id":"c8ae4dec-ce5f-441d-a2d9-a52f3ce2a4ee","arxiv_id":"2607.16879","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A nearly complete complexity map of parity-constrained graph colourings: for two, three, and four-plus colours, almost every constraint combination is NP-complete, with ∨⋆ for q≥3 left open.","lead":"The paper classifies many graph-colouring problems where each vertex has even/odd rules about how many neighbours share its colour. It settles almost every case as either easy (polynomial) or NP-complete, leaving one variant open for three or more colours.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Claim 67 in §4.2.5 is false as stated, but the 1?/∨? reductions are repairable; as written the completeness proof for these cells is not rigorous.","rationale":"The paper's strongest claim is a complete complexity dichotomy for a large family of parity-constrained colouring problems. I focused on the one cell family flagged by the reader, because if it fell, the completeness of the tables would fail. The reader is right that Claim 67 is false: for i≥2 the degree is q, not q+1, and the forward colouring demonstrates this. However, the false claim is not load-bearing in the way stated. The subsequent monochromaticity argument can be justified from Claim 68 alone: since all q−1 clique neighbours have distinct colours different from x_i's, the ?-constraint forbids the external neighbour from taking any of those colours; if it took a different colour it would duplicate. So the external neighbour is forced to match x_i. This is a simple replacement, not a new idea. For x_1 the degree-q+1/pigeonhole/parity argument works. The more serious as-written issue is Theorem 65: p_i is used but never defined, and the degree-4 count confirms the construction is missing a pendant. With the pendant supplied, the forward colouring is valid and the reverse argument is coherent. Therefore this is a presentation/correctness-of-text concern, not a demonstrated mathematical counterexample. It still warrants a CONDITIONAL verdict because the text as printed does not prove the cells; a reader cannot verify the classification without making these repairs. I agree with the reader's overall conditional but only partially with the specific diagnosis.","tokens_in":44417,"tokens_out":33946,"duration_ms":299582,"concrete_test":"Attempt the following repair and verify it step by step: (i) in Theorem 65, attach a pendant p_i^v to each x_i^v and set c(p_i^v)=c(y_i^v)=c(x_i^v) in the forward direction; re-check that x_i^v then has exactly three own-coloured neighbours (y_i, p_i, external) and one other-coloured neighbour. (ii) in Theorem 66, delete Claim 67 and prove the external neighbour of each x_i^v equals c(x_i^v) using Claim 68 alone, as described above. If both steps go through, the NP-hardness of 1?/∨? for q≥3 is supported despite the typos; if either step fails, produce an explicit colouring of the gadget that violates the claimed monochromaticity.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The completeness claim in Tables 2–3 for 1?- and ∨?-colouring with q≥3 rests on Theorems 65 and 66, and both proofs have as-written defects. In Theorem 66, Claim 67 states every x_i^v has degree q+1 and at least three same-coloured neighbours; this is false for i≥2 (degree q), and the authors' own forward colouring gives those vertices exactly one same-coloured neighbour (the external one). The intended conclusion — that each added edge is monochromatic — can be recovered without Claim 67: for i≥2, Claim 68 says the q−1 clique neighbours of x_i^v have pairwise distinct colours, none equal to c(x_i^v), so they already contain each other colour exactly once; hence the external neighbour must also be c(x_i^v), or some other colour would appear twice and violate the ?-constraint. For x_1, degree q+1 plus parity forces the external neighbour, the pendant, and the subdivision vertex to have c(x_1^v). So the q≥4 proof is fixable. The q=3 proof (Theorem 65) has a more direct gap: the construction never defines the vertices p_i, yet the forward colouring assigns c(p_i), and the reverse proof uses that each x_i has degree 4; without a pendant, x_i has degree 3 and the written colouring gives x_i two same-coloured neighbours, violating 1?. Supplying a pendant p_i on each x_i (as the figure suggests) repairs the proof. Thus the central classification is not contradicted, but the text as printed does not establish those cells.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":44820,"tokens_out":14943,"duration_ms":139440,"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":[{"comment":"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.","section":"§4.2.5, Theorem 65 (q = 3)"},{"comment":"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","section":"§4.2.5, Theorem 66, Claim 67 and following"}],"minor_comments":[{"comment":"The statement says 'an stc satisfying Πtac'; this should be 'Πstc'.","section":"Lemma 1"},{"comment":"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).","section":"Theorem 66, final paragraph"},{"comment":"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).","section":"§2 Preliminaries"},{"comment":"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.","section":"Theorem 65 / Figure 34"}],"recommendation":"major_revision","confidential_remarks":"The flaws in §4.2.5 are localized and appear readily repairable: Theorem 65 needs the pendants to be added explicitly, and Theorem 66 needs Claim 67 replaced by the direct Claim 68-based parity argument. I found no indication that the classification itself is wrong, but the two proofs as printed do not support the corresponding cells of the tables. I recommend major revision rather than rejection, and I would expect the corrected proofs to make the paper publishable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a genuinely useful classification paper, and the reader's main complaint is fair — the proof of the q≥3 1?/∨? hardness has a couple of as-written defects — but the defects look repairable, not fatal. The two-symbol framing unifies proper, defective, exact defective, odd, and strong odd colouring in a clean way, and the table entries give a complete picture up to the one open case (∨⋆, q≥3). That alone makes it worth reading for anyone working on colouring variants.\n\nWhat's new: the framework itself, plus a pile of NP-completeness results for combinations that hadn't been studied (e.g., 22 for q=2, several q≥3 cells). The polynomial cases in §3.3 are argued uniformly with GF(2) systems and look solid. The reductions from defective colouring, proper colouring, edge-colouring, and graph covering are mostly standard but checkable; I didn't find circularity. The one self-citation (odd colouring hardness from Belmonte–Sau) is legitimate because that result is established.\n\nThe soft spots are exactly where the reader put them. Claim 67 in §4.2.5 states every x_i has degree q+1; in the construction only x_1 does. The claim is used to force the external neighbour to share the colour, so the written proof has a gap. The stress-test note shows a repair: for i≥2, Claim 68 already gives all other colours exactly once, so the external neighbour must match x_i's colour; for x_1, the degree argument works. So the q≥4 proof is recoverable. Theorem 65 has a more direct gap: p_i is never defined in the construction, yet the forward colouring assigns c(p_i), and the reverse argument assumes degree 4 for x_i when it's actually 3. Adding a pendant per x_i fixes it, as the figure suggests. These are real as-written errors, but they don't suggest the classification is wrong.\n\nOther minor annoyances: several gadget properties are 'easy to verify' with figures missing (though the tables link to proofs). The structure — main text plus appendix-style sections — makes it hard to check the whole classification at once.\n\nBottom line: someone should referee this seriously. The classification is likely correct and useful, but the text as submitted does not prove the two hardest cells. I'd send it to review with a request to fix §4.2.5, define p_i, and move the missing figures into the text. After that, I'd probably cite it.","headline":"Worth serious refereeing: a useful classification with two as-written gaps in the q≥3 hardness proofs that look repairable, not fatal.","tokens_in":45309,"tokens_out":2346,"would_cite":true,"duration_ms":22453,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C15","05C85","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["graph colouring","parity constraints","odd colouring","strong odd colouring","defective colouring","NP-completeness","edge-colouring","regular graphs"],"falsifier":"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.","tokens_in":44316,"feed_emoji":"🎨","tokens_out":7830,"duration_ms":69143,"temperature":0.7,"pith_summary":"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.","feed_headline":"All parity-constrained colourings classified—one open case","feed_subtitle":"Proper, defective, and odd colouring sit in one 10×10 table whose entries are polynomial time or NP-complete.","key_machinery":"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","core_discovery":"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","pith_inferences":["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."],"forward_implications":["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."],"fun_headline_variants":["Parity colouring: full dichotomy, one open case","Colouring parity constraints: poly or NP-complete","Parity-constrained colouring: classification complete, one gap","Dichotomy for parity colourings, except one case"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Parity colouring: full dichotomy, one open case","Colouring parity constraints: poly or NP-complete","Parity-constrained colouring: classification complete, one gap","Dichotomy for parity colourings, except one case"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000142,"raw_usage":{"total_tokens":991,"prompt_tokens":718,"completion_tokens":273,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":462,"completion_tokens_details":{"reasoning_tokens":206}},"tokens_in":462,"tokens_out":273,"duration_ms":3150,"temperature":1.0,"reasoning_tokens":206,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T19:43:06.596568+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}