{"id":"690ede40-152f-4247-9f28-5d01ccc6c734","arxiv_id":"1908.03172","paper_version":1,"verdict":"CONDITIONAL","confidence":"LOW","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Planar graphs with girth at least 5 are (3,4)-colorable: their vertices admit a partition into a subgraph of maximum degree 3 and a subgraph of maximum degree 4.","lead":"Every planar graph whose shortest cycle has length at least 5 can have its vertices split into two parts, with each vertex having at most 3 same-part neighbours in one part and at most 4 in the other. This is the first known defective coloring result for these graphs with the two degree bounds summing to 7 or less.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 2.2's recoloring of a removed 3-vertex does not check that its neighbors stay within (3,4)-degree bounds; without this lemma, 3-vertices have no discharging rule.","rationale":"The reader identified the recoloring framework as the weakest part and specifically mentioned Lemma 2.2, but the reader's stated weakest assumption was Lemma 2.3. My reading agrees that the recoloring steps are fragile, but the most concrete and load-bearing failure is in Lemma 2.2: the proof asserts that a (3,4)-coloring of H extends to G by coloring v with a color appearing twice among the added vertices, without checking the color-class degrees of v1,v2,v3. This is not a mere omission of detail; the proposed extension can fail if any vi is already saturated in that color. Since Lemma 2.2 is used to eliminate 3-vertices before discharging, and the discharging rules and final-charge lemma explicitly rely on the absence of 3-vertices, the central proof is incomplete as written. The theorem may still be true, but the argument presented does not establish it. I therefore recommend moving the verdict from CONDITIONAL to REJECT for the current version, while noting that a repaired proof of Lemma 2.2 or a revised discharging rule for 3-vertices could change this assessment.","tokens_in":19637,"tokens_out":18922,"duration_ms":183418,"concrete_test":"Check Lemma 2.2 directly: in the graph H constructed in the proof, let c=φ(u1)=φ(u2), and for each i∈{1,2,3} compute n_i, the number of c-colored neighbors of vi in H. The proposed coloring of v with c is valid only if n_i≤c−1 for every i. The proof gives no such bound. Test: search for a girth-5 planar instance satisfying the proof's setup in which some vi has n_i=c (for example, a 5-vertex with two 3-colored u-neighbors and two further 3-colored neighbors). Verify that assigning v color c then violates the (3,4)-bound and that the paper offers no alternative recoloring. If such an instance is compatible with the minimality assumptions, Lemma 2.2 fails and the discharging argument must be extended to cover 3-vertices.","verdict_should_be":"REJECT","load_bearing_attack":"Lemma 2.2 is load-bearing: it removes all 3-vertices from the minimum counterexample, so the discharging proof only needs to handle degrees 2, 4, 5, 6, 7, and 8+. If 3-vertices exist, each has initial charge −1 and receives nothing under rules (R1)–(R3), so Lemma 3.5 would not cover them. The proof of Lemma 2.2 removes a 3-vertex v and forms H by adding vertices u1,u2,u3 on paths between v1,v2,v3. It then takes a (3,4)-coloring of H and argues that if φ(u1)=φ(u2)=c, coloring v with c works because every vi has a neighbor in {u1,u2}. That reasoning only shows v itself is within its color-class bound (d(v)=3≤c). It does not address the neighbors: each vi may already have c same-colored neighbors in H, and adding v as another c-colored neighbor would make vi's c-degree equal to c+1, violating the maximum degree allowed in that color class. The proof contains no estimate of the c-degree of the vi's in H and no recoloring of the vi's. Consequently, Lemma 2.2 is not established as written, and the discharging argument in Section 3 has no rule for 3-vertices.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves that every planar graph with girth at least 5 admits a vertex partition into two sets inducing subgraphs of maximum degree at most 3 and 4, respectively. The proof uses a minimal counterexample, structural lemmas on forbidden configurations, and a discharging argument. This would be the first (d1,d2)-coloring result with d1+d2≤7 for planar graphs of girth 5.","tokens_in":19877,"tokens_out":9948,"duration_ms":98046,"significance":"If correct, Theorem 1.2 is a genuine improvement over the previous best (3,5)-coloring and narrows the answer to Question 1.3 to d_2∈{2,3,4}. The paper is self-contained and follows the standard discharging paradigm. However, the current proof has a serious gap in Lemma 2.2 that affects the discharging analysis.","major_comments":[{"comment":"The final step of the proof is not justified. After fixing φ(u1)=φ(u2)=c, the authors assert that coloring v with c gives a (3,4)-coloring of G because each vi has a neighbor in {u1,u2}. This only ensures that v itself has at most 3 same-colored neighbors. It does not check whether a neighbor vi that is already colored c in H would exceed its allowed c-degree when v is added. If vi already has c same-colored neighbors in H, then after adding v its c-degree becomes c+1, violating the definition. No bound on the c-degree of the vi's in H nor any recoloring of the vi's is given. Since Lemma 2.2 is the only argument excluding 3-vertices, and the discharging rules (R1)-(R3) give nothing to 3-vertices, Lemma 3.5's assertion d(u)≠3 is unsupported. The proof of Theorem 1.2 is therefore incomplete.","section":"Lemma 2.2"},{"comment":"In the proof, after selecting a non-recolorable j-saturated neighbor u of v, the claim 'if d(u)≤8, then x must be i-saturated' is not generally true. A recoloring of u with i can be impossible because u itself would acquire i+1 i-colored neighbors, even if no i-colored neighbor of u is saturated. For example, if u has exactly i i-colored neighbors, then d(u)=1+j+i=8, consistent with d(u)≤8. The structural conclusions (i)-(iii) rely on this assertion and are used throughout the case analyses in Lemmas 2.4-2.7 and 3.2-3.4; the argument needs to handle the alternative that u has i i-colored neighbors.","section":"Lemma 2.3"}],"minor_comments":[{"comment":"The title contains a typo: 'GIR TH' should be 'GIRTH'.","section":"Title"},{"comment":"The notation 'd3 2' is garbled; it should be typeset as d_2^3 or described in words.","section":"Section 1, Question 1.3"},{"comment":"The expression 'µ∗(f)≥ 7−4−max{...}' is confusing because 7−4 is the initial charge; consider writing 3−max{...}.","section":"Lemma 3.1"},{"comment":"The phrase 'distributes its charge evenly to each incident 5p-, 5s-, and 6p-vertex (if any exist)' is ambiguous when the face has two 2-vertices; please clarify whether the equal split includes the 2-vertices.","section":"Section 3, rules (R3d)"},{"comment":"The arXiv preprint [8] is cited as 'ArXiv e-prints, March 2016'; please update with the journal reference if available.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"The gap in Lemma 2.2 is the main obstacle; if the authors can fix the recoloring, the rest of the discharging may be sound. Given the paper's length and the density of the case analysis, I recommend a thorough revision rather than a desk rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take. The theorem is new and the discharging skeleton is substantial. If the proof holds, this is the first (3,4)-coloring result for planar graphs with girth at least 5, improving the known (3,5) bound and narrowing the open problem. The structural lemmas and case analyses are detailed, not a routine scan.\n\nThe soft spot is Lemma 2.2, and the stress-test note is right. The proof removes a 3-vertex v, adds paths between its neighbors, takes a (3,4)-coloring of H, then colors v with the common color of two of the new vertices. That only checks v itself is within its color-class bound. It does not ensure each neighbor vi stays within its bound when v is added. The sentence 'using the color φ(u1) on v gives a (3,4)-coloring of G' is exactly the step that needs an estimate of the c-degree of v1,v2,v3 in H, and I don't see one. Since Lemma 2.2 is what eliminates all 3-vertices from the minimal counterexample, the discharging in Section 3 has no rule for them. That's load-bearing, not a cosmetic gap.\n\nThe rest of the paper looks careful. Lemmas 2.4-2.7 and the discharging rules are detailed, and the special-face figures make the case analysis checkable. I did not find an obvious error there, though I did not verify every case line by line. The citation pattern is clean, and the newness claim checks out.\n\nSo: the result is probably true, but as written this proof has a hole. The authors need to either fix the recoloring in Lemma 2.2 or find a way to handle 3-vertices in the discharging. I'd recommend sending this to peer review with a request for revision—the result is important enough, and the framework is promising, that a referee should engage.","headline":"The (3,4)-coloring theorem is new and the discharging framework is substantial, but Lemma 2.2 has a load-bearing gap: recoloring the removed 3-vertex ignores the effect on its neighbors' color-class degrees.","tokens_in":20457,"tokens_out":3942,"would_cite":false,"duration_ms":38826,"reading_group":"maybe","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 planar graph with girth at least 5 admits a (3,4)-coloring: its vertices split into two parts with internal maximum degrees 3 and 4.","keywords":["improper coloring","defective coloring","(3,4)-colorability","planar graph","girth at least 5","discharging method","vertex partition","maximum degree"],"falsifier":"Exhibit a planar graph with girth at least 5 whose vertex set cannot be split into a part of maximum degree at most 3 and a part of maximum degree at most 4. The theorem asserts no such graph exists, so one example would refute it; a more local check would be to find, inside a supposed minimal counterexample, a vertex of degree at most 8 whose deletion leaves no non-recolorable saturated neighbor of the type promised by Lemma 2.3.","tokens_in":19388,"feed_emoji":"🎨","tokens_out":15075,"duration_ms":130326,"temperature":0.7,"pith_summary":"The paper establishes that planar graphs with no cycles of length 3 or 4 can be partitioned into two parts with bounded internal degree: one part has maximum degree at most 3 and the other at most 4. Equivalently, every such graph is $(3,4)$-colorable in the defective-coloring sense. This is the first known pair of allowed degrees summing to 7 for this class, improving the previous $(3,5)$ bound, and it narrows the open question of the best $(3,d)$ pair to three candidates: $d=2,3,4$. The significance is that a mild sparsity condition, namely girth at least 5, already forces a very uneven but still bounded two-way partition of the vertex set.","feed_headline":"Girth-5 planar graphs split into degree-3 and degree-4 parts","feed_subtitle":"First pair of allowed degrees summing to at most 7; narrows the open (3,d) question to d = 2, 3, or 4.","key_machinery":"The engine of the proof is a minimal-counterexample analysis combined with discharging. The central structural lemma (Lemma 2.3) asserts that in a minimal counterexample, deleting any vertex of degree at most 8 forces the existence of a saturated neighbor that cannot be recolored, with precise type guarantees (for example, a 4-saturated neighbor that is either a $9^+$-vertex or a $6^{s+}$-vertex). Saturated here means the neighbor already carries its full quota of same-colored neighbors. This lemma is used to rule out many face configurations. The discharging phase begins with initial charge $\\mu(x)=d(x)-4$ on every vertex and face; Euler's formula makes the total charge $-8$, and the rules (R1), (R2), and (R3) redistribute charge so that each vertex and face ends nonnegative, a contradiction. Special named configurations such as poor, semi-poor, and rich vertices, heavy edges, and the face types $F_{5a},\\dots,F_7$ carry the bookkeeping.","core_discovery":"The paper proves Theorem 1.2: every planar graph whose shortest cycle has length at least 5 admits a $(3,4)$-coloring, meaning its vertices can be split into two parts $A$ and $B$ such that each vertex of $A$ has at most 3 neighbors in $A$ and each vertex of $B$ has at most 4 neighbors in $B$. This is the first pair of allowed degrees with sum at most 7 known to work for all such graphs, improving the earlier $(3,5)$ result. The proof assumes a minimal counterexample and derives a rigid local structure: there are no 3-vertices, every edge is incident with a vertex of degree at least 5, and faces can carry only limited combinations of low-degree and poor vertices. A discharging argument then assigns initial charge $d(x)-4$ to every vertex and face, moves charge by explicit rules, and shows every element ends with nonnegative charge, contradicting Euler's formula, which fixes the total charge at $-8$.","pith_inferences":["Beyond the paper, the same discharging scheme might be adapted to attack $(3,3)$- or even $(3,2)$-colorability by strengthening Lemma 2.3 for low-degree vertices; the paper does not claim such a strengthening.","Beyond the paper, because planarity enters only through Euler's formula and face lengths, an analogous discharging proof may extend to graphs on surfaces with sufficiently large girth, though the charge targets would change.","Beyond the paper, a computer search over all planar graphs of girth 5 up to moderate order for $(3,4)$-, $(3,3)$-, and $(3,2)$-colorings could test how close these bounds are to sharp and would give a concrete target for a counterexample if one exists."],"forward_implications":["Every planar graph with girth at least 5 now has a vertex partition into a part of maximum degree at most 3 and a part of maximum degree at most 4, improving the previous $(3,5)$-colorability bound.","Because a known construction shows girth-5 planar graphs need not be $(3,1)$-colorable, the optimal second parameter in the $(3,d)$ question is now known to lie in $\\{2,3,4\\}$.","Since the result holds for every planar graph with girth at least 5, it automatically covers all planar graphs with larger girth, including triangle-free and 4-cycle-free families.","The discharging bookkeeping isolates the finite family of local configurations that any minimal counterexample would have to contain; if the theorem is right, none of those configurations can actually occur."],"supporting_citations":[{"why":"Previous result that planar graphs with girth at least 5 are (3,5)-colorable; the paper improves it.","marker":"[9]"},{"why":"Showed planar graphs with girth at least 5 are (4,4)-colorable, part of the known sum-at-least-8 regime.","marker":"[16]"},{"why":"Implied (2,6)-colorability of planar graphs with girth at least 5, another previous bound in the known regime.","marker":"[6]"},{"why":"Provides constructions showing girth-4 planar graphs are not (d1,d2)-colorable and girth-5 planar graphs are not (3,1)-colorable, setting the sharpness context.","marker":"[14]"},{"why":"Established (1,10)-colorability for graphs with girth at least 5, completing the known classification the introduction summarizes.","marker":"[7]"}],"fun_headline_variants":["First (3,4)-coloring for all girth-5 planar graphs","Girth-5 planar graphs now (3,4)-colorable","Sum≤7 coloring achieved for girth-5 planar graphs","Planar girth-5 graphs split into degree-3 and 4"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof depends on the assertion that in a smallest counterexample, deleting a vertex of degree at most 8 always leaves a neighbor that already has its full quota of same-colored neighbors and cannot be recolored, with exactly the degree and type guarantees the later lemmas use; if that recoloring analysis is wrong anywhere, the discharging argument loses its foundation.","fun_headline_variants_meta":{"raw":{"variants":["First (3,4)-coloring for all girth-5 planar graphs","Girth-5 planar graphs now (3,4)-colorable","Sum≤7 coloring achieved for girth-5 planar graphs","Planar girth-5 graphs split into degree-3 and 4"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000611,"raw_usage":{"total_tokens":2900,"prompt_tokens":1062,"completion_tokens":1838,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":678,"completion_tokens_details":{"reasoning_tokens":1758}},"tokens_in":678,"tokens_out":1838,"duration_ms":13171,"temperature":1.0,"reasoning_tokens":1758,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:23:33.559070+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhibit a planar graph with girth at least 5 whose vertex set cannot be split into a part of maximum degree at most 3 and a part of maximum degree at most 4. The theorem asserts no such graph exists, so one example would refute it; a more local check would be to find, inside a supposed minimal counterexample, a vertex of degree at most 8 whose deletion leaves no non-recolorable saturated neighbor of the type promised by Lemma 2.3.","supporting_citations":[{"cited_title":"Planar graphs with girth at least 5 are (3 , 5)-colorable","cited_arxiv_id":null,"evidence_quote":"Previous result that planar graphs with girth at least 5 are (3,5)-colorable; the paper improves it."},{"cited_title":"List improper colorings of planar graphs with prescribed girth","cited_arxiv_id":null,"evidence_quote":"Showed planar graphs with girth at least 5 are (4,4)-colorable, part of the known sum-at-least-8 regime."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Implied (2,6)-colorability of planar graphs with girth at least 5, another previous bound in the known regime."},{"cited_title":"Montassier and P","cited_arxiv_id":null,"evidence_quote":"Provides constructions showing girth-4 planar graphs are not (d1,d2)-colorable and girth-5 planar graphs are not (3,1)-colorable, setting the sharpness context."},{"cited_title":"(1 , k)-coloring of graphs with girth at least five on a surface","cited_arxiv_id":null,"evidence_quote":"Established (1,10)-colorability for graphs with girth at least 5, completing the known classification the introduction summarizes."}],"review_version":1}