{"id":"287b844b-e0d5-4e48-821b-df4908c85880","arxiv_id":"2411.15336","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"New constructions show planar graphs can fail 3-defective 3-correspondence colorings, a 1-defective 3-correspondable but not 4-correspondable planar graph exists, and all outerplanar graphs are 3-defective 2-correspondence colorable, but a load-bearing lemma is false.","lead":"This paper proves new bounds for defective correspondence coloring of planar graphs, including a planar graph that is 1-defective 3-correspondable but not 4-correspondable. One key lemma in that proof is false, so the main theorem is not established as written.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The proof of Theorem 1.4 collapses: Lemma 5.4(i) is false, as shown by a valid correspondence cover of R with no 1-defective coloring keeping def(c)=0.","rationale":"The reader's strongest claim is Theorem 1.4, and the reader's weakest assumption is Lemma 5.4(i). I re-examined the lemma and the counterexample supplied by the reader. The cover is a legitimate correspondence cover of R: the edges respect the matching condition for each edge of R, and all matchings are maximal. The exhaustive argument over the two possible colors for c is correct: def(c)=0 forces one of the two remaining vertices into a degree-2 defect. Thus Lemma 5.4(i) is genuinely false. I then checked where Lemma 5.4(i) is used. It appears directly in Lemmas 7.2, 7.4, 7.5, and 7.7, which together with symmetric cases prove Lemma 7.1, which is the engine behind Lemma 5.9. It also appears in Lemma 8.1 and Lemma 8.2, which feed Lemma 5.10. The proof of Lemma 7.2, for instance, colors R1 with def(z)=0 and then colors R2 with the remaining color at z; if Lemma 5.4(i) fails, the second step may not be possible, and the union may not be 1-defective. No alternative argument is supplied for these steps. The first and third theorems (Theorems 1.3 and 1.6) appear not to depend on this lemma, so the paper may be partially salvageable. However, the submitted proof of Theorem 1.4 is invalid as written. The reader's REJECT verdict is therefore appropriate; my stress-test does not change it.","tokens_in":23009,"tokens_out":4941,"duration_ms":41686,"concrete_test":"Brute-force check the specific cover of R with lists {a1}, {b1,b2}, {c1,c2}, {d1,d2} and edges a1-b1, a1-d1, b1-c1, b2-c2, c1-d2, c2-d1, b1-d2, b2-d1. Enumerate all 4 assignments of (b,c,d) with a=a1 and verify that no assignment has both max defect ≤1 and def(c)=0. The search returns no valid coloring, confirming that Lemma 5.4(i) is false.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Lemma 5.4(i) claims that every correspondence cover of R with lists {a1}, {b1,b2}, {c1,c2}, {d1,d2} has a 1-defective coloring with def(c)=0. This is false. Consider the cover whose matching edges are a1-b1, a1-d1, b1-c1, b2-c2, c1-d2, c2-d1, b1-d2, b2-d1. Since a is forced to a1, any coloring must choose b in {b1,b2}, c in {c1,c2}, d in {d1,d2}. If c=c1, then def(c)=0 forces b=b2 and d=d1, but then d is adjacent to both a1 and b2, giving def(d)=2. If c=c2, then def(c)=0 forces b=b1 and d=d2, but then b is adjacent to both a1 and d2, giving def(b)=2. No other assignment keeps def(c)=0, so no 1-defective coloring with def(c)=0 exists. The proof of Lemma 5.4(i) itself fails in Case 2: the proposed coloring φ(b)=b1, φ(c)=c2, φ(d)=d2 gives b1 two defects, and the symmetric fallback gives the same problem. Because Lemma 5.4(i) is explicitly used in Lemmas 7.2, 7.4, 7.5, 7.7, and 8.1, 8.2 (and in the symmetric cases covered by 7.6, 7.8, 8.3-8.7), the concatenation of the two halves R1 and R2 at the shared vertex z relies on being able to keep def(z)=0 in one half. With Lemma 5.4(i) invalid, Lemma 7.1 and Lemma 5.10 are not established, so the proof that T(4) is 1-def 3-correspondable in Theorem 5.11 does not go through. The non-4-correspondability part (Section 9) appears independent, but the central construction of Theorem 1.4 is unsupported as written.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies defective correspondence coloring of planar graphs. It claims three main results: (i) there is a planar graph that is not 3-defective 3-correspondable (Theorem 1.3); (ii) there is a planar graph that is 1-defective 3-correspondable but not 4-correspondable, extending a recent result of Ma, Xu, and Zhu from list coloring to correspondence coloring (Theorem 1.4); and (iii) every outerplanar graph is 3-defective 2-correspondable, with 3 defects best possible (Theorem 1.6). The proof of Theorem 1.4 is built around a gadget T(4) formed from four copies of a graph T identified at two vertices, with Section 5 setting up the reduction, Sections 6-8 proving the 1-defective 3-correspondability direction, and Section 9 proving the failure of 4-correspondability. The outerplanar and Theorem 1.3 arguments are independent of the T(4) construction. The main defect of the manuscript is that a central lemma used to combine colorings across the two halves of T is false as stated, and the proof of Theorem 1.4 collapses as a result.","tokens_in":23373,"tokens_out":19696,"duration_ms":171553,"significance":"If Theorem 1.4 were correct, it would be a genuine separation result: a planar graph that is 1-defective 3-correspondable but not 4-correspondable would extend the Ma-Xu-Zhu list-coloring example to the correspondence setting, where matchings may vary per edge. Theorems 1.3 and 1.6 are also interesting contributions to the defective correspondence coloring literature, and the non-4-correspondability construction in Section 9 is explicit and appears self-contained. However, the 1-defective 3-correspondability direction of the main theorem rests on Lemma 5.4(i), which admits a concrete counterexample. The manuscript is not a reliable proof of Theorem 1.4 as written, although the other two main theorems may well survive independently.","major_comments":[{"comment":"Lemma 5.4(i) is false as stated. Consider the correspondence cover of R with L(a)={a1}, L(b)={b1,b2}, L(c)={c1,c2}, L(d)={d1,d2} and edges a1b1, a1d1, b1c1, b2c2, c1d2, c2d1, b1d2, b2d1. All matchings in this cover are maximal. Since φ(a)=a1 is forced, if φ(c)=c1 then def(c)=0 forces φ(b)=b2 and φ(d)=d1, giving def(d)=2 because d1 is adjacent to both a1 and b2. If φ(c)=c2 then def(c)=0 forces φ(b)=b1 and φ(d)=d2, giving def(b)=2 because b1 is adjacent to both a1 and d2. Hence no 1-defective H-coloring has def(c)=0, contradicting the lemma. The proof of the lemma fails in Case 2, where the proposed assignment φ(b)=b1, φ(c)=c2, φ(d)=d2 creates exactly the second defective vertex in this cover.","section":"§5.1, Lemma 5.4(i)"},{"comment":"The invalidity of Lemma 5.4(i) is load-bearing for the proof of Theorem 1.4, not a peripheral gap. The concatenation arguments in Lemmas 7.2, 7.3, and 7.7 use Lemma 5.4(i) precisely to obtain a coloring of one half of T with zero defect at the shared vertex z; this is exactly the false conclusion def(c)=0 when z plays the role of c. Lemma 7.7, Case 2 is representative: the proof chooses φ(z)=z1 with def φ(z)=0 and then colors the other half with only a 1-defective coloring, so if the first half could only guarantee def φ(z)≤1, the total defect at z could become 2. The counterexample from my first comment is a cover of R that is neither wedged nor twisted, so it can occur in a good cover of T\\{u,v} in the case ℓ(x)=1, ℓ(z)=2, ℓ(y)=2, which is automatically good under Definition 5.6. Consequently Lemma 7.1, Lemma 5.9, and Theorem 5.11, and therefore the 1-defective 3-correspondability half of Theorem 1.4, are not established. Section 9's proof of non-4-correspondability appears independent of this lemma, but the two halves of Theorem 1.4 together are unsupported as written.","section":"§7–§8, dependence on Lemma 5.4(i)"}],"minor_comments":[{"comment":"In the displayed definition of E(H) for a list cover, the text reads \"c= d}}\" with a doubled closing brace and an unspaced equality; this should be \"c = d\" and a single closing brace.","section":"§2, Definition 2.1"},{"comment":"In the final paragraph of the proof of Lemma 8.7, the sentence \"if ψ is the coloring induced by ... then ψ is a 1-defective H coloring φ of T\" mixes the names ψ and φ; the last symbol should be ψ.","section":"§8, Lemma 8.7"},{"comment":"In Case 2 of the proof of Theorem 4.1, the line \"with ψ2(v) ⩽ 1 and ψ2(z) ⩽ 2\" should read \"with def ψ2(v) ⩽ 1 and def ψ2(z) ⩽ 2\" for clarity.","section":"§4, Theorem 4.1 proof, Case 2"}],"recommendation":"reject","confidential_remarks":"The reader's counterexample to Lemma 5.4(i) is correct and I have verified it independently against the definitions in the manuscript. The error is central: the proof of Theorem 1.4's 1-defective 3-correspondability direction relies on the false def(c)=0 conclusion to control the shared vertex z when combining the two halves of the gadget. The paper also contains two other results (Theorems 1.3 and 1.6) that appear independent of this lemma, and Section 9's non-4-correspondability construction looks sound; if the author can repair the good-case analysis, a resubmission focused on those parts may be viable. But as submitted, the main theorem is not proven, so I recommend rejection rather than major revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a well-written paper with two plausible results and one false key lemma. Theorem 1.4 is not established because Lemma 5.4(i) is wrong.\n\nWhat's good: Theorem 1.3 strengthens the Cho et al. decomposition obstruction to an actual non-correspondability statement, and Theorem 1.6 gives a clean sharp result for outerplanar graphs. The exposition is careful, the lemma structure makes the long proof navigable, and the constructions are explicit. Citations are on point.\n\nThe critical problem is Lemma 5.4(i). The cover of R with lists {a1}, {b1,b2}, {c1,c2}, {d1,d2} and edges a1-b1, a1-d1, b1-c1, b2-c2, c1-d2, c2-d1, b1-d2, b2-d1 has no 1-defective coloring with def(c)=0. If c=c1 then def(c)=0 forces b=b2 and d=d1, and d has neighbors a1 and b2; if c=c2 then def(c)=0 forces b=b1 and d=d2, and b has neighbors a1 and d2. In both cases some vertex has defect 2. This is not a corner case: the cover has maximal matchings and exact list sizes, so it falls under the paper's own standing assumptions. The proof's Case 2 selects a coloring that is not 1-defective.\n\nSince Lemma 5.4(i) is used in Lemmas 7.2-7.8 and 8.1-8.7 to combine colorings of the two halves at z, the proof of Theorem 5.11 (and hence Theorem 1.4) collapses. The non-4-correspondability half, Section 9, appears independent and may be salvageable, but the main separation result is unsupported.\n\nThe audience is specialists in defective correspondence coloring. The two side results might be of use to them, but the headline is the main draw, and it doesn't hold up. I agree with the reader's verdict. I would not send this to peer review in its current form; the correct move is a firm reject with a clear explanation of the counterexample, plus an invitation to resubmit if the author can repair the lemma or find a different construction.","headline":"Main theorem rests on a false lemma; the other two results look plausible, but the paper's headline claim is not proven as written.","tokens_in":23983,"tokens_out":8824,"would_cite":false,"duration_ms":68997,"reading_group":"no","serious_thinker":"yes","would_accept_peer_review":false},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C15","05C10"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper constructs a planar graph that is 1-defective 3-correspondable but not 4-correspondable, and shows outerplanar graphs need exactly three defects for 2-correspondence coloring.","keywords":["defective coloring","correspondence coloring","DP-coloring","planar graphs","outerplanar graphs","list coloring","relaxed coloring"],"falsifier":"Enumerate all 3-fold correspondence covers of T(4) up to isomorphism and check each for a 1-defective coloring; if any cover has none, the positive half of the main theorem fails, and similarly, finding a proper coloring of the specific 4-fold cover constructed in Section 9 would refute the non-4-correspondability claim.","tokens_in":22673,"feed_emoji":"🎨","tokens_out":10150,"duration_ms":94824,"temperature":0.7,"pith_summary":"This paper studies defective correspondence coloring, a generalization of list coloring in which each edge carries its own matching between color lists and each vertex may share its color with up to d neighbors. Its central result is a planar graph that is 1-defective 3-correspondable, meaning every triple of lists with edge-specific matchings admits a coloring where each vertex matches at most one neighbor, yet is not 4-correspondable, meaning some four-list cover forces a proper-coloring obstruction. This extends to correspondence coloring a separation previously established for list coloring. The paper also builds a planar graph that is not 3-defective 3-correspondable, tightening known bounds, and proves all outerplanar graphs are 3-defective 2-correspondable with three defects best possible. Together these results narrow which pairs of defect allowance and color count can hope to color every planar graph.","feed_headline":"Planar graph: 3 relaxed colors OK, 4 correspondence colors fail","feed_subtitle":"Shows a planar graph that nearly works with 3 flexible lists can still fail with 4 strict ones","key_machinery":"The load-bearing object is the gadget T, formed by two copies R1 and R2 of K4-minus-an-edge sharing a central vertex z, with endpoint colors for u and v fixed by the partial coloring. A correspondence cover of each half is classified as twisted when it contains a specific 6-cycle of conflicts and wedged when it contains a smaller conflict pattern; the lemmas use these two patterns to decide whether a 1-defective coloring with zero defect on z exists. The counting lemma then shows that for any 3-fold cover, only six of the nine (u,v) color pairs are bad, so with four copies of T there is a pair that is good for at least two copies. That pair is colored through the extension lemmas, and the four-copy graph is the configuration that makes the counting work; the non-4-correspondability direction is carried by a permutation-based 4-fold cover that blocks every proper coloring.","core_discovery":"The main construction is the graph T(4): four copies of a twelve-vertex gadget T glued by identifying the x-vertices and identifying the y-vertices. The paper proves that every 3-fold correspondence cover of T(4) has a 1-defective coloring, while a carefully chosen 4-fold cover has no proper coloring at all. The proof works by classifying the two halves of T, each half being K4 with one edge deleted, as twisted or wedged depending on which conflict cycles appear in the cover, then showing that among the nine possible color pairs for the shared endpoints u and v, at most six pairs can be bad in a sense that forces an extra defect. Counting over the four copies leaves a good pair that can be colored with zero defect on u and v, while the 4-fold obstruction is built from a permutation construction on the four copies. The paper also establishes that some planar graph fails 3-defective 3-correspondability, and that outerplanar graphs need exactly three defects for two-list correspondence coloring.","pith_inferences":["The twisted/wedged classification is checkable by brute force: for the small cover types that appear after fixing u and v, exhaustive enumeration would independently confirm the counting lemmas and could be reused for larger gadgets.","If the T(4) construction is as flexible as it appears, similar identified-copy gadgets should produce separations for other defect and list-size pairs, such as d-defective 3-correspondability versus d+1-correspondability for small d.","The outerplanar theorem suggests that on graphs of bounded treewidth, defective correspondence coloring may track defective list coloring with the defect threshold shifted by one; series-parallel graphs would be a natural test class.","Because the non-4-correspondability cover is built from permutations on the four copies, varying the permutation family could probe whether the threshold is sharp, for example whether T(3) is already 1-defective 3-correspondable."],"forward_implications":["The main construction answers a question asked for list coloring in the correspondence setting: 1-defective 3-correspondability does not imply 4-correspondability for planar graphs.","Combining Theorem 1.3 with known decomposition results leaves the smallest d for which every planar graph is d-defective 3-correspondable between 4 and 6.","The graph witnessing Theorem 1.3 is 4-correspondable, so a planar graph can be properly 4-correspondable and still fail to be 3-defective 3-correspondable.","Every outerplanar graph is 3-defective 2-correspondable, and the fan-based construction shows that two defects do not suffice.","The same framework leaves open whether the separating graph could be chosen not 4-choosable, which would strengthen the break with list coloring."],"supporting_citations":[{"why":"Introduces correspondence coloring and the cover formalism used throughout the paper.","marker":"[7]"},{"why":"Supplies the list-coloring result, a planar graph that is 1-def 3-choosable but not 4-choosable, that Theorem 1.4 extends to correspondence coloring.","marker":"[17]"},{"why":"Provides the foundational defective coloring results for planar and outerplanar graphs that frame the questions and the outerplanar theorem.","marker":"[5]"},{"why":"Proves outerplanar graphs are 2-def 2-choosable, the list-coloring analog that Theorem 1.6 generalizes to correspondence coloring.","marker":"[8]"},{"why":"Independently proves outerplanar graphs are 2-def 2-choosable and poses defective choosability questions relevant to the paper's open problems.","marker":"[21]"},{"why":"Provides edge-decomposition results yielding the 2-def 4-correspondable and 6-def 3-correspondable upper bounds that frame Theorems 1.3 and the remaining threshold questions.","marker":"[4]"}],"fun_headline_variants":["Planar graph: 3 relaxed lists OK, 4 strict fail","1-defective 3-correspondable planar graph, not 4-correspondable","For a planar graph: 3 lists need 1 defect, 4 lists fail","3 lists: 1-defective coloring works; 4 lists: proper coloring fails","Planar graph: with 3 lists it's 1-defective, with 4 it's impossible"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The positive half of the main construction depends on Lemma 5.4(i), which asserts that every assignment of conflict matchings to the four-vertex half-gadget R, with one vertex given one color and three vertices given two colors, admits a 1-defective coloring in which the special vertex c is left with zero defect.","fun_headline_variants_meta":{"raw":{"variants":["Planar graph: 3 relaxed lists OK, 4 strict fail","1-defective 3-correspondable planar graph, not 4-correspondable","For a planar graph: 3 lists need 1 defect, 4 lists fail","3 lists: 1-defective coloring works; 4 lists: proper coloring fails","Planar graph: with 3 lists it's 1-defective, with 4 it's impossible"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.002224,"raw_usage":{"total_tokens":8598,"prompt_tokens":932,"completion_tokens":7666,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":548,"completion_tokens_details":{"reasoning_tokens":7554}},"tokens_in":548,"tokens_out":7666,"duration_ms":51812,"temperature":1.0,"reasoning_tokens":7554,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T14:29:33.235428+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate all 3-fold correspondence covers of T(4) up to isomorphism and check each for a 1-defective coloring; if any cover has none, the positive half of the main theorem fails, and similarly, finding a proper coloring of the specific 4-fold cover constructed in Section 9 would refute the non-4-correspondability claim.","supporting_citations":[{"cited_title":"Dvoˇ r´ ak and L","cited_arxiv_id":null,"evidence_quote":"Introduces correspondence coloring and the cover formalism used throughout the paper."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the list-coloring result, a planar graph that is 1-def 3-choosable but not 4-choosable, that Theorem 1.4 extends to correspondence coloring."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the foundational defective coloring results for planar and outerplanar graphs that frame the questions and the outerplanar theorem."},{"cited_title":"Eaton and T","cited_arxiv_id":null,"evidence_quote":"Proves outerplanar graphs are 2-def 2-choosable, the list-coloring analog that Theorem 1.6 generalizes to correspondence coloring."},{"cited_title":"ˇSkrekovski","cited_arxiv_id":null,"evidence_quote":"Independently proves outerplanar graphs are 2-def 2-choosable and poses defective choosability questions relevant to the paper's open problems."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides edge-decomposition results yielding the 2-def 4-correspondable and 6-def 3-correspondable upper bounds that frame Theorems 1.3 and the remaining threshold questions."}],"review_version":1}