{"id":"ca1b5c74-3488-4935-a98e-ef9fcd32c6d1","arxiv_id":"1908.04902","paper_version":4,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Every planar graph with no triangles normally adjacent to 8−-cycles, no 4-cycles normally adjacent to 6−-cycles, and no normally adjacent 5-cycles is 3-choosable.","lead":"This paper proves that a broad class of planar graphs, those with no 'normally adjacent' short cycles, can be colored from lists of three colors. It also proves these graphs split into an independent set plus a forest, extending a line of results on 3-choosability.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 2.8's identification step is under-verified: it checks only normal adjacency to triangles, not the other forbidden adjacencies in the class G.","rationale":"The reader's weakest_assumption identifies Lemma 2.8, and I agree that this is the most load-bearing structural step. The lemma is under-proved: the proof concentrates on newly created cycles avoiding normal adjacency to triangles, while the class G has three separate forbidden normal-adjacency conditions, and the identification of u1 and v3 can in principle create new short cycles that are normally adjacent to existing 4-, 5-, or 6-cycles. If any case is missed, G* leaves the class, and the induction argument in Lemma 2.9 cannot be applied. I do not have a concrete counterexample, and the gap may well be repairable with a more careful case analysis, so this does not warrant rejection. The reader's CONDITIONAL verdict remains appropriate, sharpened by this specific gap. Secondary weaknesses noted by the reader are also real: Section 3 is explicitly a sketch with discharging deferred, and the final section discusses open problems rather than tightness despite the abstract's claim. However, these do not affect the main 3-choosability theorem as directly as Lemma 2.8.","tokens_in":20634,"tokens_out":12300,"duration_ms":123187,"concrete_test":"Re-derive Lemma 2.8 by exhaustive local enumeration. Fix f = [v1v2...vl] with l = 4 or 5 and all vi internal 3-vertices, and list every plane configuration of Γ that satisfies Lemmas 2.1 and 2.2(e) and contains a u1-v3 path P with |E(P)| = 7 or 8, the only lengths that can create a new 8^-cycle after identification. For each configuration, identify u1 and v3 and test membership of G* in G with a small script: for every pair of cycles in G* of lengths (3, <=8), (4, <=6), and (5,5), check whether they share exactly one edge and their union is an (l1+l2-2)-cycle with exactly one chord. If no forbidden pair is found for all enumerated configurations, the lemma survives; the first configuration yielding a forbidden pair disproves it.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central proof of Theorem 1.6 depends on Lemma 2.9 eliminating internal (3,3,3,3)- and (3,3,3,3,3)-faces, and Lemma 2.9 depends entirely on Lemma 2.8, which claims that identifying u1 and v3 in Γ yields a graph G* still in G. The proof of Lemma 2.8 is incomplete. It splits on whether u2 lies on a u1-v3 path P and tries to bound |E(P)|, but the claims 'It is easy to check' and 'It is observed' carry the argument: case (i) concludes |E(P)| <= 8 only if |E(P)| = 8 and Q is a separating abnormal 11-cycle; case (ii) derives |E(P)| >= 7. Even granting these bounds, the text only argues that newly created 7- or 8-cycles are not normally adjacent to 3-cycles. Membership in G also forbids 4-cycles normally adjacent to 6^-cycles and normally adjacent 5-cycles. The proof never checks those, nor does it check that the identification does not create a new short cycle normally adjacent to an existing short cycle through a shared edge elsewhere on P. The sentence 'there are no 3-cycles normally adjacent to abnormal cycles' appears misdirected, since abnormal cycles are 11-/12-cycles and the relevant condition concerns triangles and 8^-cycles. If one configuration of a length-7 or length-8 path P creates a new cycle normally adjacent to a 4-, 5-, or 6-cycle, then G* is not in G, the induction in Lemma 2.9 collapses, and the discharging rules, which rely on the absence of (3,3,3,3)- and (3,3,3,3,3)-faces, cannot be applied.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies plane graphs in the class G, defined by forbidding triangles normally adjacent to 8^-cycles, 4-cycles normally adjacent to 6^-cycles, and normally adjacent 5-cycles. The main result, Theorem 1.6, is a 'weakly' DP-3-coloring statement: if S has size at most 12 and is either a single vertex or the vertex set of a normal cycle, then any precoloring of G[S] that is consistent on closed walks of length three extends to an M-coloring of G. This yields Theorem 1.7, that every graph in G is 3-choosable, and the corollaries that planar graphs without 4-,6-,8-cycles and without 4-,5-,7-,8-cycles are 3-choosable. Section 3 states an analogous superextension theorem for IF-colorings, giving a near-bipartite partition result, and Section 4 discusses tightness and open problems. The proof of Theorem 1.6 follows the standard minimal-counterexample and discharging framework, with structural lemmas on short faces and a vertex-identification reduction in Lemma 2.8.","tokens_in":21028,"tokens_out":11742,"duration_ms":112762,"significance":"If the proofs are completed, the results are significant. Theorem 1.7 generalizes the 3-choosability theorems of Dvořák-Postle and Liu-Li, and Corollaries 1.8 and 1.9 give clean new sufficient conditions. The IF-coloring result extends a recent result of Liu and Yu. The overall strategy is sound in outline: the paper extends external benchmarks rather than fitting parameters to a target conclusion, and the discharging rules R1-R8 are explicit and checkable. The paper also honestly discusses the limitations of the method in Remark 2 and Section 4. No circularity was found in the main argument; the only self-citation, Theorem 1.16, is used as a tool rather than as the target claim. The main concerns are completeness of key structural proofs, not the architecture of the proof.","major_comments":[{"comment":"The proof that G* belongs to G is the load-bearing step of the reduction, but it is not written in sufficient detail. The two cases are concluded by 'It is easy to check' and 'It is observed' assertions that are not derived: in case (i) the claim that |E(P)|≤8 forces |E(P)|=8 and Q to be a separating abnormal 11-cycle, and in case (ii) the equality characterizations |Q1|=|Q2|=6 for |E(P)|=7 and |Qi|=6, |Q3-i|=7 for |E(P)|=8. These claims are exactly what rule out new short cycles after identifying u1 and v3. In addition, the sentence 'there are no 3-cycles normally adjacent to abnormal cycles' is used as if it were part of the definition of G; it must be derived from the unproved Observation on abnormal cycles. The preservation of the other two forbidden adjacency conditions under the identification should also be stated explicitly rather than left to the phrase 'satisfies the requirement for adjacency in Theorem 1.6'. Since Lemma 2.9 removes internal (3,3,3,3)- and (3,3,3,3,3)-faces using exactly this reduction, and the discharging rules depend on that removal, a complete proof of Lemma 2.8 is required before the main theorem can be accepted.","section":"§2, Lemma 2.8"},{"comment":"Theorem 3.1 is announced and then only a 'Sketch of a proof' is provided. The reader is told that the structural lemmas are the same and that 'the discharging part is the same with that in Theorem 3.1', and Lemma 3.2 is placed in an appendix with the note that it 'will be deleted in the published version'. As a consequence, the IF-coloring theorem, which is highlighted in the abstract and yields Theorem 3.2, is not actually proved in the manuscript. Please provide a complete proof or a precise reduction to Section 2 that specifies how the IF-coloring superextension property is handled in each structural lemma and in the discharging phase.","section":"§3, Theorem 3.1"},{"comment":"The Observation following Theorem 1.6 (every edge on an abnormal 12^-cycle is contained in a 4-, 5-, 6- or 7-cycle, and every vertex not on a normal 12^-cycle O has at most two neighbors on O) is used in Lemma 2.2(g), Lemma 2.8, and in the face-charge analysis, but no proof is given. Since the abnormal cycles are the finite list in Fig. 1, a short explicit verification should be included; currently this is an unproved load-bearing assertion.","section":"§1, Observation"}],"minor_comments":[{"comment":"The phrase 'it is showed' should be 'it is shown'.","section":"Abstract"},{"comment":"The proof of Lemma 3.3 refers to 'Lemma 2.1', but Lemma 2.1 states that every 8^-cycle has no chords; the intended reference appears to be Lemma 2.3.","section":"§3, Lemma 3.3"},{"comment":"In the last paragraph of the proof, the statement 'By the adjacency of cycles, x2x3 is only contained in a unique triangle' should be justified briefly: because two triangles sharing an edge would be normally adjacent, and G has no triangles normally adjacent to 8^-cycles.","section":"§2, Lemma 2.4"},{"comment":"In the step where a chord w1w2 is added to form G', the text says 'We can easily check that G' is a plane graph satisfying the assumption of Theorem 1.6'; please spell out why the new graph remains in G and why the matching assignment remains consistent on closed walks of length three.","section":"§2, Lemma 2.2(f)"},{"comment":"The sentence in the appendix that the proof of Lemma 3.2 'will be deleted in the published version' should be removed; the submitted manuscript should be self-contained.","section":"Appendix"}],"recommendation":"major_revision","confidential_remarks":"The central 3-choosability theorem is plausible and the proof strategy is standard and promising. The main obstacle is the under-verified Lemma 2.8 and the sketch-level presentation of Section 3; both are local and presumably fillable, so I recommend major revision rather than rejection. The authors should also ensure that Theorem 1.16, which is said to be derivable from their own preprint [16], is stated precisely and that the preprint is publicly available and accessible."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The main thing to know: the paper proves a genuinely broader 3-choosability theorem than Liu-Li or Dvořák-Postle, using a new forbidden-adjacency class G and the notion of abnormal cycles. The discharging proof for Theorem 1.6 follows the standard template and is detailed in Section 2. The corollaries are clean, and the idea of allowing precolored normal cycles rather than faces is a real strengthening.\n\nThe soft spots are real but localized. Lemma 2.8 is the one I'd worry about. It claims that identifying u1 and v3 in Γ keeps G* in G. The proof splits on whether u2 lies on the path P and establishes distance bounds, but the checks that the new 7- and 8-cycles are not normally adjacent to forbidden small cycles only consider triangles. The class G also forbids 4-cycles normally adjacent to 6^-cycles and normally adjacent 5-cycles; those cases are never checked. The sentence about \"no 3-cycles normally adjacent to abnormal cycles\" is beside the point, since abnormal cycles are 11/12 and the forbidden patterns concern 8^- cycles. Both \"easy to check\" and \"observed\" carry real weight here, and this is load-bearing: Lemma 2.9 depends on it, and the discharging rules assume the absence of (3,3,3,3)- and (3,3,3,3,3)-faces. If a missed case creates a 4-cycle normally adjacent to a 6-cycle, the induction collapses. I think the gap is fillable, but it needs to be written out.\n\nSecond, Section 3 is a sketch. The discharging for the IF-coloring theorem is not given; saying \"the discharging part is the same\" isn't enough when the structural setup differs. And the abstract says \"tightness is discussed\" but the final section only poses open problems. That's an overstatement.\n\nOn the citation side, the use of Theorem 1.16 from the authors' own preprint is legitimate—it's a tool, not the target. The paper is honest about prior work.\n\nWho should read it: anyone working on 3-choosability or DP-coloring of planar graphs. I'd bring it to the reading group, but I'd tell them to read Lemma 2.8 with pencil in hand. For peer review: yes, it deserves a serious referee. A revised version with the identification lemma fully proved and the IF-coloring details filled in would be a solid contribution.","headline":"Genuine extension of the known 3-choosability results, but the pivotal Lemma 2.8 is under-verified and the IF-coloring section is a sketch.","tokens_in":21565,"tokens_out":5713,"would_cite":false,"duration_ms":52575,"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":"Every plane graph in the class $\\mathscr{G}$ — with no triangle normally adjacent to an $8^{-}$-cycle, no $4$-cycle normally adjacent to a $6^{-}$-cycle, and no normally adjacent $5$-cycles — is $3$-choosable, proved through a stronger…","keywords":["planar graph","3-choosability","list coloring","DP-coloring","normally adjacent cycles","discharging method","IF-coloring","near-bipartite"],"falsifier":"Look for a graph in $\\mathscr{G}$ containing an internal 4- or 5-face whose every vertex has degree 3, glue together the two vertices $u_1$ and $v_3$ as Lemma 2.8 does, and check whether a new cycle of length at most 8 becomes normally adjacent to a 3-cycle; such a graph would be a direct counterexample to Lemma 2.9. A small exhaustive search over plane graphs in $\\mathscr{G}$ with such a face would settle the claim.","tokens_in":20459,"feed_emoji":"🎨","tokens_out":12452,"duration_ms":106116,"temperature":0.7,"pith_summary":"The paper proves that every plane graph in the class $\\mathscr{G}$ — no triangle normally adjacent to an $8^{-}$-cycle, no $4$-cycle normally adjacent to a $6^{-}$-cycle, and no normally adjacent $5$-cycles — admits a proper list coloring from lists of size $3$. The proof establishes a stronger 'weakly DP' statement: any consistent $3$-matching-assignment coloring of a set $S$ of at most $12$ vertices, where $S$ is a single vertex or the vertices of a normal cycle, extends to the whole graph. Two cycles are normally adjacent when they share exactly one edge, and a normal cycle is any cycle that is not one of the two exceptional 11- or 12-cycles. This extension theorem implies the $3$-choosability of the whole class, and as corollaries it settles two previously open list-coloring cases: planar graphs without $4$-, $6$-, $8$-cycles and planar graphs without $4$-, $5$-, $7$-, $8$-cycles are both $3$-choosable. A companion theorem shows every graph in $\\mathscr{G}$ also admits an IF-coloring, a partition of the vertices into an independent set and a set inducing a forest.","feed_headline":"Planar graphs without normally adjacent short cycles are 3-choosable","feed_subtitle":"A weak DP-coloring theorem extends precolorings of small normal cycles, settling two open list-coloring cases.","key_machinery":"The load-bearing mechanism is the minimal-counterexample reduction combined with discharging. Structural lemmas, especially Lemma 2.8, show that identifying a vertex $u_1$ with a vertex $v_3$ of an internal face keeps the reduced graph inside $\\mathscr{G}$, which lets a precoloring of the smaller graph extend back to the original vertices. The discharging rules assign initial charges $\\deg(v)-4$ to vertices and $\\deg(f)-4$ to faces, redistribute them along incidences, and force every element to nonnegative final charge with at least one positive, contradicting the standard charge-sum identity for plane graphs. Two supporting tools are essential: a renaming lemma that makes the edges of a consistently covered subgraph straight, and a cover-coloring result stating that a cycle with a 2-list cover that is neither of the two exceptional ladder covers admits a coloring, used to rule out internal faces whose vertices all have degree three.","core_discovery":"The central claim is Theorem 1.7: every graph in $\\mathscr{G}$ is $3$-choosable, where $\\mathscr{G}$ is the class of plane graphs without triangles normally adjacent to $8^{-}$-cycles, without $4$-cycles normally adjacent to $6^{-}$-cycles, and without normally adjacent $5$-cycles. To obtain it, the authors prove Theorem 1.6, a weak DP-coloring extension result: if $S$ has at most $12$ vertices and is either a single vertex or a normal cycle, then every consistent $3$-matching-assignment coloring of $G[S]$ extends to an $M$-coloring of $G$. Here $M$-coloring means a proper coloring of the DP cover, and the consistency condition is imposed only on closed walks of length three. The proof runs by minimal counterexample, structural lemmas showing that every $8^{-}$-cycle has no chords and that certain internally degree-three faces cannot occur, and a discharging argument that redistributes charges until a contradiction is reached. The same machinery yields Theorem 1.15: every graph in $\\mathscr{G}$ has an IF-coloring, i.e., its vertex set partitions into an independent set and a set inducing a forest.","pith_inferences":["The same discharging architecture may transfer to neighboring forbidden-cycle classes: relaxing the adjacency condition on $5$-cycles would make the theorem imply DP-$3$-colorability of planar graphs without $3$-, $6$-, $7$-cycles, an open problem the paper names explicitly.","The existence of exceptional abnormal 11- and 12-cycles shows the precoloring-extension statement is genuinely tight; a natural testable extension is to classify all minimal obstructions to extension when the cycle is abnormal.","Because the IF-coloring theorem comes from the same structural lemmas, the near-bipartite conclusion is likely not an isolated fact: one could probe whether nearby classes, such as graphs without $3$-, $7$-, $8$-cycles, also admit IF-colorings, another open problem listed in the paper."],"forward_implications":["Every planar graph without $4$-, $6$-, $8$-cycles is $3$-choosable.","Every planar graph without $4$-, $5$-, $7$-, $8$-cycles is $3$-choosable.","Every graph in $\\mathscr{G}$ is IF-colorable: its vertices can be partitioned into an independent set and a set inducing a forest.","The main theorem improves the earlier $3$-choosability result for planar graphs without adjacent cycles of length at most $8$, allowing adjacent cycles of length $6$ to $8$ and replacing face precolorings by precolorings of normal cycles."],"supporting_citations":[{"why":"Introduces DP-coloring, the consistency condition on closed walks of length three, and the renaming lemma used to make edges straight throughout the proof.","marker":"[5]"},{"why":"The theorem being improved: 3-choosability of planar graphs without adjacent cycles of length at most eight.","marker":"[11]"},{"why":"Provides the cover-coloring result used to eliminate internal faces whose incident vertices all have degree three.","marker":"[16]"},{"why":"Together with the preceding reference, supplies the cycle-cover coloring theorem invoked in Lemma 2.9.","marker":"[8]"},{"why":"The previous IF-coloring result for planar graphs without 4-, 6-, 8-cycles, which the paper extends to the whole class.","marker":"[15]"}],"fun_headline_variants":["Weak DP-coloring settles two planar list-coloring open cases","Planar graphs with no normally adjacent short cycles: 3-choosable","Weak DP-coloring proves 3-choosability for planar graphs with no normal cycle adjacencies","Planar graphs with no normal short-cycle adjacencies are 3-choosable"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Everything rests on Lemma 2.8's claim that when the two vertices $u_1$ and $v_3$ are glued together, no new forbidden short cycle is created; if that case analysis misses a path, the reduced graph falls outside $\\mathscr{G}$ and the induction cannot proceed.","fun_headline_variants_meta":{"raw":{"variants":["Weak DP-coloring settles two planar list-coloring open cases","Planar graphs with no normally adjacent short cycles: 3-choosable","Weak DP-coloring proves 3-choosability for planar graphs with no normal cycle adjacencies","Planar graphs with no normal short-cycle adjacencies are 3-choosable"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.003377,"raw_usage":{"total_tokens":12767,"prompt_tokens":1037,"completion_tokens":11730,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":653,"completion_tokens_details":{"reasoning_tokens":11640}},"tokens_in":653,"tokens_out":11730,"duration_ms":75902,"temperature":1.0,"reasoning_tokens":11640,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:28:29.574038+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Look for a graph in $\\mathscr{G}$ containing an internal 4- or 5-face whose every vertex has degree 3, glue together the two vertices $u_1$ and $v_3$ as Lemma 2.8 does, and check whether a new cycle of length at most 8 becomes normally adjacent to a 3-cycle; such a graph would be a direct counterexample to Lemma 2.9. A small exhaustive search over plane graphs in $\\mathscr{G}$ with such a face would settle the claim.","supporting_citations":[{"cited_title":"Dvořák and L","cited_arxiv_id":null,"evidence_quote":"Introduces DP-coloring, the consistency condition on closed walks of length three, and the renaming lemma used to make edges straight throughout the proof."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The theorem being improved: 3-choosability of planar graphs without adjacent cycles of length at most eight."},{"cited_title":"Cover and variable degeneracy","cited_arxiv_id":"1907.06630","evidence_quote":"Provides the cover-coloring result used to eliminate internal faces whose incident vertices all have degree three."},{"cited_title":"Kim and K","cited_arxiv_id":null,"evidence_quote":"Together with the preceding reference, supplies the cycle-cover coloring theorem invoked in Lemma 2.9."},{"cited_title":"Liu and G","cited_arxiv_id":null,"evidence_quote":"The previous IF-coloring result for planar graphs without 4-, 6-, 8-cycles, which the paper extends to the whole class."}],"review_version":1}