{"id":"d3cfe509-6768-4ff1-8a06-2a478c9a4ed2","arxiv_id":"2504.21821","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Every planar graph is weakly degenerate with list sizes f(v) ≥ max{7-g(v),2}, proving the correspondence-colouring analogue of local-girth choosability.","lead":"This paper proves a conjecture about colouring planar maps when the number of allowed colours at each vertex depends on the shortest cycle through that vertex. The proof unifies several famous results in graph colouring into a single stronger theorem about weak degeneracy.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Observation 2.6, used to justify every reduction to a smaller canvas, is false as stated; deleting a vertex can destroy the girth-3 status of a B-vertex, so the smaller tuple need not be a canvas.","rationale":"The reader identified the 2- and 3-chord classifications in Lemmas 3.12/3.13 as the weakest structural assumption. My stress-test found an earlier, more basic obstacle: the preservation observation that underpins those classifications is not true. The four-vertex example shows that a single deletion can destroy the unique triangle that made a B-vertex of girth 3, so the same triple (G-v,P,A,B,f) is not a canvas. This matters because the proof's minimal-counterexample argument repeatedly deletes subgraphs and immediately applies Observation 2.6 before carrying out the induction. At minimum, the paper must revise Observation 2.6 to specify how A and B are updated and recheck all later claims; this is a proof gap rather than a demonstrated false theorem. The main theorem may well be true and the gap may be patchable, but the current proof is not complete as written, so ACCEPT is too strong; CONDITIONAL seems the appropriate verdict. Lemma 3.11 is also stated without proof, though it appears unused, which is a secondary concern.","tokens_in":36075,"tokens_out":16781,"duration_ms":188595,"concrete_test":"Verify the claimed counterexample to Observation 2.6 by checking all canvas axioms for the 4-vertex graph above, then checking the same axioms in G-u. If confirmed, audit every application of Observation 2.6 and re-run the proofs of Lemmas 3.6 and 3.12 with B' = {v in B : g_{G-X}(v)=3} replacing B; in particular, verify that f(v)=2 for removed B-vertices satisfies (C4c) and that no exceptional canvas of type (X1) or (X3) is accidentally created. If Lemmas 3.12 and 3.13 still hold, the classification and main theorem may be salvageable; if not, the minimal-counterexample argument collapses.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The main proof is a minimal-counterexample induction whose reductions all rely on Observation 2.6: deleting vertices from a canvas leaves a canvas. This is false as stated. Example: let G be the plane graph with vertices b,u,v,w, outer cycle b-u-v-w-b and chord u-w; set P = vw, A = ∅, B = {b}, f(b)=2, f(u)=3, f(v)=f(w)=0. Then g_G(b)=3 and (G,P,A,B,f) is an unexceptional canvas. Delete u. The remaining graph is the path b-w-v, so b no longer lies on any cycle; the tuple (G-u,P,A,B,f) violates (C3), because B must consist of vertices of girth 3. Thus Observation 2.6 is false as written. The observation is invoked in Lemmas 3.4, 3.5, 3.6, 3.7, 3.8, 3.12 and 3.13, so every 'by Observation 2.6, the smaller object is an unexceptional canvas' step is unjustified unless B is redefined after each deletion. A patch is conceivable—remove from B any vertex that no longer has girth 3 and note that f=2 still satisfies (C4c)—but the paper does not state this, and the chord classifications in Lemmas 3.12/3.13 are exactly where the exact membership of B matters for exceptions (X1) and (X3).","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves that every planar graph is weakly f-degenerate for every local girth function f, i.e. f(v) ≥ max{7−g(v),2}; as a corollary it proves Postle and Smith-Roberge's conjecture that every planar graph is local girth correspondence colourable. The proof is by minimal counterexample to a stronger induction statement (Theorem 2.8) formulated in terms of canvases with a distinguished outer-face path P and two independent sets A and B of vertices with restricted f-values. Sections 3–5 establish structural properties of a minimum counterexample, remove a path R from the outer face, and handle the two possible failures of the resulting reduced canvas. The argument is detailed and, apart from the gaps noted below, appears to be self-contained.","tokens_in":1348,"tokens_out":1657,"duration_ms":125431,"significance":"If the proof is correctly repaired, this is a strong and significant result: it simultaneously strengthens weak 4-degeneracy of planar graphs and weak 2-degeneracy of planar girth-5 graphs, resolves the correspondence-colouring conjecture of Postle and Smith-Roberge, and does so with a self-contained argument whose exceptions are three finite configurations rather than infinite families. The paper also honestly discusses why its methods do not yield exponential colouring bounds. These are substantial strengths. The main concern is technical; I believe it is addressable, but it affects the foundation of the induction.","major_comments":[{"comment":"Observation 2.6 is false as stated. Consider the plane graph with outer cycle b-u-v-w-b and chord u-w, and let P=vw, A=∅, B={b}, f(b)=2, f(u)=3, f(v)=f(w)=0. This is an unexceptional canvas: b has girth 3, u satisfies (C4d), and v and w lie in P. Deleting u leaves the path b-w-v, in which b has infinite girth, so (G-u,P,A,B,f) violates (C3) and is not a canvas. The observation is invoked at the start of Lemmas 3.4, 3.5, 3.6, 3.7, 3.8, 3.12 and 3.13, and similar reasoning is used in Sections 4 and 5; the induction steps as written are therefore not justified. A repair is plausible: after deleting vertices, redefine B as the subset of the old B that still has girth 3 in the smaller graph, since girth can only increase under vertex deletion and f=2 still satisfies (C4c). Because vertex deletion cannot create new adjacencies, exceptionality cannot newly arise. However, this repair must be stated explicitly and checked in every invocation; it is not a harmless rephrasing, since the classifications in Lemmas 3.12 and 3.13 depend on the exact membership of B in exceptions (X1) and (X3).","section":"Observation 2.6 (Section 2)"},{"comment":"Several canvas checks in Sections 4 and 5 are asserted very tersely, for example 'it is easy to check that w∈\\widehat B' in Claim 1 and the verification that the final operations in Section 5 are legal. Since the false Observation 2.6 is used elsewhere, these checks need to be written out in full under the corrected understanding of how B and \\widehat B are updated after vertex deletion. The current level of detail is not sufficient for a proof whose main mechanism is repeated reduction to a smaller canvas.","section":"Sections 4 and 5"}],"minor_comments":[{"comment":"This lemma is stated without proof and is not used later in the paper. Either provide the proof or remove the statement, since an unproved lemma in a minimal-counterexample proof is a formal gap.","section":"Lemma 3.11"},{"comment":"The text says that exceptional canvases are not weakly f-degenerate because fK assigns a negative value to some vertex. For type (X3), the defining adjacencies give fK(v1)=fK(v2)=0, so this justification is not accurate; if the sentence is only motivational, it should be reworded.","section":"Section 2, after Definition 2.5"},{"comment":"The cases for defining R are described as lexicographically minimal without explicit mutually exclusive conditions. This is understandable, but later arguments depend on knowing exactly which case applies, so the cases should be stated with clean disjoint conditions.","section":"Section 3.2, cases (R1)–(R8)"},{"comment":"The step 'it is easy to check that w∈\\widehat B' should be expanded: one should explicitly verify that w has girth 3 in \\widehat G and that \\widehat f(w)=2, especially since the proof of (C3) depends on this membership.","section":"Claim 1, Section 4"}],"recommendation":"major_revision","confidential_remarks":"To the editor: the reader's positive assessment of the overall structure is justified, and the paper is a serious contribution if the technical gap is closed. However, the false Observation 2.6 is genuinely load-bearing: almost every reduction to a smaller canvas currently cites it. I recommend major revision rather than rejection because the repair (redefining B after each deletion) appears local and compatible with the existing proof architecture. The authors should be asked to replace Observation 2.6 with a corrected and proved statement, or to remove it and verify each invocation individually."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe paper proves a big conjecture—local girth correspondence colourability of planar graphs—by establishing a stronger weak degeneracy statement. If correct, it unifies Thomassen's two list-colouring theorems with the recent weak degeneracy results, and it replaces two infinite exception families from Postle–Smith-Roberge with a handful of finite exceptions. That is a genuine result, and the authors have done serious work: the canvas framework is carefully set up, the exceptions are explicit, and the proof is largely self-contained. It is not a parameter scan or a restatement.\n\nThe problem is that a load-bearing observation is false as stated. Observation 2.6 says removing vertices from a canvas leaves a canvas. That is not true: deleting a vertex can destroy the girth-3 status of a B-vertex, because B requires vertices of girth exactly 3. Concrete example: take the plane graph on b,u,v,w with outer cycle b-u-v-w-b and chord u-w, with P=vw, A=∅, B={b}, f(b)=2, f(u)=3, f(v)=f(w)=0. This is an unexceptional canvas; deleting u leaves a tree where b has infinite girth, so the tuple is no longer a canvas. Observation 2.6 is invoked in Lemmas 3.4–3.8, 3.12, and 3.13 to conclude the smaller object is an unexceptional canvas. Those steps are unsupported as written. The likely patch is to redefine B after each deletion (drop vertices that lost girth 3; f=2 still satisfies the relevant lower bound), and similarly for A if needed. But the chord classifications in 3.12/3.13 depend on exact B membership, so the patch is not completely trivial and needs to be checked.\n\nThere are minor issues too: Lemma 3.11 is stated without proof and never used; the proof is long and not machine-checked. Those are not serious by themselves.\n\nMy bottom line: the central idea and the structure of the proof are plausible, and the theorem is important enough that the paper should go to a serious referee. The referee should focus on Observation 2.6 and every place it is used. If the patch works, this is a strong paper. As it stands, the proof is not complete.","headline":"A significant conjecture-resolution with a real gap: Observation 2.6, used throughout the induction, is false as stated, though the proof is likely patchable.","tokens_in":36955,"tokens_out":4603,"would_cite":false,"duration_ms":47274,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C15","05C10"],"pacs":[],"model":"deepseek-v4-flash","headline":"Planar graphs are weakly degenerate under local girth bounds","keywords":["weak degeneracy","planar graphs","local girth","correspondence colouring","DP-colouring","list colouring","canvas","DelSave operation"],"falsifier":"Conduct a brute-force search over all plane graphs with at most ten vertices for a canvas $(G,P,A,B,f)$ satisfying Definition 2.5 with no (X1)--(X3) structure, for which the associated function $f_K(v)=f(v)-|N(v)\\cap P|$ admits no legal Del/DelSave deletion sequence of $G-P$. Such a canvas would directly falsify Theorem 2.8 and hence the main theorem. Alternatively, exhibit a planar graph $G$ and the canonical local girth function $f(v)=\\max\\{7-g(v),2\\}$ with no legal weak-degeneracy sequence; Theorem 1.11 says none exists.","tokens_in":35883,"feed_emoji":"🎨","tokens_out":10274,"duration_ms":95360,"temperature":0.7,"pith_summary":"The paper proves a local-girth analogue of weak degeneracy for planar graphs. For each vertex $v$, define its local girth $g(v)$ as the length of a shortest cycle through $v$; the theorem says that whenever a function $f$ gives each vertex at least $\\max\\{7-g(v),2\\}$ units, every planar graph admits a legal deletion sequence using the Del and DelSave operations. This is strictly stronger than ordinary degeneracy, and it directly implies the conjectured correspondence-colouring (DP-colouring) version of the local girth list colouring theorem. A sympathetic reader should care because one statement simultaneously explains the three classical pillars of planar list colouring: 5-list-colourability, 4-list-colourability when triangles are absent, and 3-list-colourability when girth is at least five. The proof works by establishing a much more detailed inductive statement about 'canvases' with exactly three small exceptional shapes.","feed_headline":"Planar graphs are weakly degenerate under local girth bounds","feed_subtitle":"This proves the correspondence-colouring conjecture and unifies three classical list-colouring results.","key_machinery":"The load-bearing object is the canvas: a tuple $(G,P,A,B,f)$ in which $G$ is a plane graph, $P$ is an acceptable path or cycle on the outer face (a path of at most four vertices with a girth condition on its internal vertices), $A$ and $B$ are independent sets on the outer face boundary outside $P$ consisting of vertices of girth at least five (with $f=1$) and girth three (with $f=2$), and $f$ satisfies the local girth lower bounds (C4a)--(C4e). The induction removes not just a few vertices but an arbitrarily long path $R$ along the outer face, chosen according to eight case rules (R1)--(R8) that depend on the values of $f$; the corresponding deletion sequences (D1)--(D8) simulate a coordinated colour choice using Del and DelSave. Two structural chord lemmas classify every 2- and 3-chord in a minimum counterexample as belonging to one of the three exceptional canvas types, which is what guarantees that after a path removal the remaining smaller canvas still satisfies the induction hypothesis unless exactly one of $A$ or $B$ loses independence. Those two failure modes are then handled in Sections 4 and 5 by deleting the offending vertices and checking that the resulting smaller canvas is unexceptional.","core_discovery":"The central discovery is Theorem 1.11: if $G$ is planar and $f$ is a local girth function, meaning $f(v)\\ge \\max\\{7-g(v),2\\}$ for every vertex $v$, then $G$ is weakly $f$-degenerate. In the paper's language, weak $f$-degeneracy means there is a legal sequence of operations $\\mathrm{Del}(v)$ and $\\mathrm{DelSave}(v,w)$ that removes every vertex of $G$, where Del decrements all neighbours of $v$ and DelSave decrements all neighbours except the chosen neighbour $w$, with legality requiring $f(v)>f(w)$ for a save. The theorem is proved through the more restrictive canvas statement (Theorem 2.8): every canvas $(G,P,A,B,f)$ — a plane graph with an acceptable path or cycle $P$ on the outer face, independent sets $A$ and $B$ of vertices with extra-restricted values, and specified lower bounds on $f$ — is weakly $f$-degenerate unless it exhibits one of three exceptional configurations (X1), (X2), or (X3). Taking $P$ to be a single edge on the outer face recovers Theorem 1.11. Since weak $f$-degeneracy with a function $f$ implies $(f(v)+1)$-correspondence colouring, the theorem resolves the conjecture that every planar graph is local girth correspondence colourable, and it does so without any infinite family of exceptional structures.","pith_inferences":["A natural next step, not taken in the paper, is to check whether the chord-classification lemmas can be re-proved for other sparse graph classes; for locally planar graphs or graphs on surfaces, the same canvas framework could transfer if the exceptional structures are adjusted.","The eight-case path removal scheme suggests a computational experiment: enumerate all legal Del and DelSave sequences for small planar graphs and measure the maximum average availability; consistent values above 1 would support the paper's availability conjecture, while a graph whose every legal sequence has average availability exactly 1 would refute it.","Because the proof is a finite-case induction, it likely yields a polynomial-time algorithm that constructs the legal deletion order; if so, the correspondence colouring result becomes constructive, not just existential."],"forward_implications":["Theorem 1.11 implies Theorem 1.7: every planar graph is local girth correspondence colourable, settling the open conjecture in that direction.","Because weak degeneracy is the more flexible parameter, the theorem also implies the analogous statement for correspondence-painting, the online version of correspondence colouring.","The theorem simultaneously recovers previously separate results: planar graphs are weakly 4-degenerate, planar graphs of girth at least five are weakly 2-degenerate, and the classical list-colouring theorems for planar graphs with girth 3, 4, and 5.","The proof does not yield an exponential lower bound on the number of colourings; the paper states this explicitly and proposes a stronger availability conjecture that, via Proposition 1.13, would give exponentially many local girth correspondence colourings."],"supporting_citations":[{"why":"It introduces weak degeneracy and supplies Lemma 2.2, the monotonicity result used to compare functions in the induction.","marker":"[3]"},{"why":"It proves that planar graphs are weakly 4-degenerate via a canvas-style inductive statement, and the path-removal reductions in Sections 4 and 5 are modelled on it.","marker":"[4]"},{"why":"It proves a precolouring extension for a length-two path in planar 5-list-colouring, whose coordinated-colouring idea is adapted to Del and DelSave operations in the exceptional canvas analysis.","marker":"[11]"},{"why":"It defines correspondence (DP) colouring, the framework in which the conjecture resolved here is stated.","marker":"[12]"},{"why":"It proves that planar graphs of girth at least five are weakly 2-degenerate, one of the two weak-degeneracy results that Theorem 1.11 jointly strengthens.","marker":"[15]"},{"why":"It establishes local girth list colourability of planar graphs, the list-colouring result whose correspondence analogue is investigated here, and the canvas framework with long-path removal is inherited from it.","marker":"[19]"},{"why":"It conjectures the correspondence analogue and provides the exponentially-many-colourings perspective that this paper does not recover.","marker":"[20]"}],"fun_headline_variants":["Local girth bounds yield weak degeneracy in planar graphs","Planar graphs: weak degeneracy from local girth","Weak degeneracy meets local girth in plane graphs","Correspondence colouring conjecture proven via weak degeneracy","Unifying planar colouring: weak degeneracy and local girth"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is the chord classification inside a minimum counterexample: Lemmas 3.12 and 3.13 assert that every 2-chord and every 3-chord whose endpoints are not internal vertices of $P$ forces one of the three exceptional canvas structures (X1), (X2), or (X3); if a chord of any other shape appeared, the induction step that removes a long boundary path could not conclude that the reduced canvas is still unexceptional.","fun_headline_variants_meta":{"raw":{"variants":["Local girth bounds yield weak degeneracy in planar graphs","Planar graphs: weak degeneracy from local girth","Weak degeneracy meets local girth in plane graphs","Correspondence colouring conjecture proven via weak degeneracy","Unifying planar colouring: weak degeneracy and local girth"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000214,"raw_usage":{"total_tokens":1488,"prompt_tokens":1072,"completion_tokens":416,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":688,"completion_tokens_details":{"reasoning_tokens":334}},"tokens_in":688,"tokens_out":416,"duration_ms":3987,"temperature":1.0,"reasoning_tokens":334,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T04:53:28.926408+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Conduct a brute-force search over all plane graphs with at most ten vertices for a canvas $(G,P,A,B,f)$ satisfying Definition 2.5 with no (X1)--(X3) structure, for which the associated function $f_K(v)=f(v)-|N(v)\\cap P|$ admits no legal Del/DelSave deletion sequence of $G-P$. Such a canvas would directly falsify Theorem 2.8 and hence the main theorem. Alternatively, exhibit a planar graph $G$ and the canonical local girth function $f(v)=\\max\\{7-g(v),2\\}$ with no legal weak-degeneracy sequence; Theorem 1.11 says none exists.","supporting_citations":[{"cited_title":"Bernshteyn and E","cited_arxiv_id":null,"evidence_quote":"It introduces weak degeneracy and supplies Lemma 2.2, the monotonicity result used to compare functions in the induction."},{"cited_title":"Dvořák, B","cited_arxiv_id":null,"evidence_quote":"It proves a precolouring extension for a length-two path in planar 5-list-colouring, whose coordinated-colouring idea is adapted to Del and DelSave operations in the exceptional canvas analysis."},{"cited_title":"Dvořák and L","cited_arxiv_id":null,"evidence_quote":"It defines correspondence (DP) colouring, the framework in which the conjecture resolved here is stated."},{"cited_title":"Weak degeneracy of planar graphs and locally planar graphs","cited_arxiv_id":"2303.07901","evidence_quote":"It proves that planar graphs of girth at least five are weakly 2-degenerate, one of the two weak-degeneracy results that Theorem 1.11 jointly strengthens."},{"cited_title":"Postle and E","cited_arxiv_id":null,"evidence_quote":"It establishes local girth list colourability of planar graphs, the list-colouring result whose correspondence analogue is investigated here, and the canvas framework with long-path removal is inherited from it."},{"cited_title":"Exponentially Many Correspondence Colourings of Planar and Locally Planar Graphs","cited_arxiv_id":"2309.17291","evidence_quote":"It conjectures the correspondence analogue and provides the exponentially-many-colourings perspective that this paper does not recover."}],"review_version":1}