{"id":"505718c6-6c60-4c1b-bb8e-b37a3eb819fd","arxiv_id":"2507.10453","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Every 3-connected non-complete planar graph is degree-truncated DP-16-colourable, and Richter's degree-truncated 6-choosability question is answered negatively even with lists of size 7.","lead":"This paper answers an open question about coloring planar graphs whose vertices get color lists sized by their degree: it constructs a 3-connected planar graph that fails even with lists of size 7, then proves every 3-connected non-complete planar graph can be colored from degree-truncated lists of size 16. The same method yields a uniform bound for every proper minor-closed family of graphs.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 3's protector existence is unproved when N_H(θ_Q') is empty, leaving GDP-tree V1-components potentially uncolourable and Theorem 4 incomplete.","rationale":"The reader's weakest assumption is precisely the gap I find: Lemma 3's proof is vacuous when N_H(θ_Q') is empty. I agree with the reader's CONDITIONAL assessment. The paper's main positive theorem relies on every GDP-tree component receiving a protector; one unprotected component breaks the coloring argument. The claim that the configuration can occur is plausible (the reader gives V2={x,y}); even if the specific example is not 3-connected, the proof does not rule out more elaborate 3-connected versions where Q connects to earlier V2-components. Thus, as written, the proof is incomplete. I do not see an independent fatal flaw in Theorem 6, and the gap appears local, so rejection is not warranted; conditional acceptance with a demand for a completed Lemma 3 is appropriate.","tokens_in":13628,"tokens_out":13639,"duration_ms":151859,"concrete_test":"Perform a computational search over all 3-connected planar graphs on at most 12 vertices (or a hand-built candidate) with a vertex partition V2 whose induced subgraph contains an edge v1v2 and a GDP-tree V1-component Q lying in a face of G[V2] whose boundary meets the relevant V2-component in exactly {v1,v2}; for the nice subgraph H returned by the constructive proof of Lemma 4, test whether N_H(θ_Q) contains v1 or v2. If any instance has N_H(θ_Q') = ∅, Lemma 3's conclusion is false for that H, and the proof needs a new argument or a different choice of H. Conversely, if every such configuration forces N_H(θ_Q) ∩ {v1,v2} ≠ ∅ under 3-connectivity, the gap is closed and Theorem 4's proof can be repaired.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 3's proof of Theorem 4 reduces to assigning each GDP-tree component Q of G[V1] a protector v ∈ N_H(θ_Q). Lemma 3 claims there is always v ∈ N_H(θ_Q') adjacent to a non-root vertex of a leaf block of Q', where θ_Q' is the face of the last V2-component G_k containing the vertices of Q visible to G_k. The proof by contradiction assumes no such v and then invokes 'Let v be the largest vertex in N_H(θ_Q') adjacent to a non-root vertex...'. This step is invalid when N_H(θ_Q') = ∅: the negation holds vacuously, yet no v exists to produce the claimed protector. The definition of a nice subgraph permits this: for a face θ_Q with d_Θ(θ_Q) = 2 (i.e., boundary reduced to two vertices v1,v2 in G_k), the lower bound d_H(θ_Q) ≥ d_Θ(θ_Q)-2 = 0 allows H to omit both v1 and v2, so V(θ_Q') = {v1,v2} and N_H(θ_Q') = ∅ is consistent with niceness. The paper neither rules this configuration out using 3-connectivity nor proves the existence of a nice H avoiding it. If such a Q is never made safe, the final application of Lemma 1 cannot colour G[V1], so Theorem 4 is unproved as written. The negative answer (Theorem 6) is a separate construction and appears sound; only the upper-bound proof is affected.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies degree-truncated k-choosability and its DP-analogue. It constructs a 3-connected non-complete planar graph that is not degree-truncated 7-choosable (Theorem 6), answering Richter's question negatively. It then claims that every 3-connected non-complete planar graph is degree-truncated DP-16-colourable (Theorem 4), and more generally that for every proper minor-closed family G with K_{s,t} not in G, every s-connected graph in G that is not a GDP-tree is degree-truncated DP-k-colourable for an explicit constant k (Theorem 5). The proofs combine the GDP-tree classification of DP-colouring, Thomason's minor-density estimates, and a protector argument based on a 'nice' subgraph H of Θ(G[V2]).","tokens_in":13837,"tokens_out":36630,"duration_ms":411645,"significance":"If the upper-bound proof is correct, the paper resolves a natural question of Richter and gives the first absolute constant for degree-truncated choosability of 3-connected planar graphs. The constants are explicit (16, and k = 2^{s+2}tq in the minor-closed case), and the construction in Theorem 6 is explicit and checkable. The use of external results (Bernshteyn-Kostochka-Pron, Thomason) is appropriate. The main concern is that the protector lemma (Lemma 3) supporting Theorem 4 is not proved for a case allowed by the nice-subgraph definition; this is a load-bearing gap, though it appears repairable.","major_comments":[{"comment":"Lemma 3 does not cover the case N_H(θ_Q') = ∅. In the proof, the assumption that no vertex of N_H(θ_Q') is adjacent to a non-root vertex of a leaf block is vacuous when N_H(θ_Q') is empty, and the statement 'Q′ has at least two leaf blocks, for otherwise every vertex of Q′ is a non-root vertex and every vertex in N_H(θ_Q′) is adjacent to a non-root vertex of Q′' does not produce a contradiction in that case. The later case analysis also fails when V(θ_Q') = {v_1, v_2}: the cycle C constructed from B_1, B_2 has V(θ_Q') - {v_1, v_2} = ∅, so the alleged contradiction with 'every vertex of V(θ_Q′) is adjacent to some vertex of Q′' is not a contradiction. Since Definition 7 permits a face of G[V_2] with d_Θ(θ) ≤ 2 to have N_H(θ) = ∅, and the last component G_k can have exactly two boundary vertices on the face containing Q′, Lemma 3 is unproved as stated. This gap is load-bearing: Lemma 3 is the only step that guarantees a GDP-tree component of G[V_1] receives a protector, and without it the final application of Lemma 1 in the proof of Theorem 4 is unsupported.","section":"Section 3, Lemma 3"},{"comment":"Independently of the empty-neighbourhood case, the path argument in the second half of Lemma 3 is not written correctly. The proof sets 'u' as the root vertex of B_1 and later concludes that P is an edge 'that connects v ∈ N_H(θ_Q′) and u ∈ U(B_1)', silently changing u from a root to a non-root vertex. Moreover, the vertex v obtained from 3-connectivity is only known to lie in V(θ_Q′); under the contradiction hypothesis it could be one of the omitted vertices v_1, v_2, in which case the conclusion v ∈ N_H(θ_Q′) does not follow. These points need to be clarified before the protector argument can be accepted.","section":"Section 3, Lemma 3, path argument"},{"comment":"The proof would be substantially clearer if the choice of the nice subgraph H were tied to the component order of G[V_2]. As written, H is fixed before the order ≺ is used, and the argument for the last component G_k depends on the unproved Lemma 3. In particular, if N_H(θ_Q) is contained entirely in earlier components, the protector rule may have already failed to protect Q before G_k is reached; the manuscript does not explain why such a configuration is impossible or why the proof can choose H to avoid it. Strengthening Lemma 2 or Lemma 3 to guarantee a usable protector in the last component would resolve this issue.","section":"Section 3, protector assignment rule"}],"minor_comments":[{"comment":"The abstract states the general theorem for graphs 'other than a GDP tree', while Theorem 3 in Section 1 states 'other than a Gallai-tree'. Since GDP-trees also include even cycles, which are not Gallai-trees, the relationship between the two statements should be spelled out explicitly.","section":"Abstract and Section 1, Theorems 3 and 5"},{"comment":"In Definition 7, the condition 'N_Θ(Γ)(θ) − N_H(θ) ⊆ V(B) for a block B of Γ' should read 'for some block B', otherwise the quantifier is ambiguous.","section":"Definition 7"},{"comment":"The verification that |L(v)| = min{d_G(v), 7} for the glued graph is delegated to 'easy to verify'; because the degrees of u_3 and v_3 increase by one after the gluing, a short table of the degrees of the vertices of H would improve readability.","section":"Section 2, Theorem 6"}],"recommendation":"major_revision","confidential_remarks":"The negative result (Theorem 6) appears sound and the overall programme is interesting. The main obstacle is Lemma 3 in the proof of Theorem 4: as written it has a genuine logical gap in the case N_H(θ_Q') = ∅, and the path argument also needs correction. I believe this is repairable, either by strengthening the nice-subgraph lemma so that faces containing V1 components have nonempty N_H, or by adding a separate argument for the two-vertex-face case. I would not reject the paper at this stage."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe headline: the counterexample to Richter's question is solid, and the constant-16 theorem is likely true, but the proof of the planar theorem has a gap that needs to be closed.\n\nWhat's genuinely new: Theorem 6 constructs a 3-connected non-complete planar graph that is not degree-truncated 7-choosable. That settles Richter's question negatively. The gadget is explicit, the non-colourability proof is checkable, and I could not find an error there. Theorems 4 and 5 are strong: a universal constant for all 3-connected non-complete planar graphs, and a version for every proper minor-closed family. The DP-framework is well chosen, and the reduction to protecting GDP-tree components is a nice idea.\n\nWhere it gets soft: the protector argument in Section 3 has a genuine hole. Lemma 3 claims there is always a vertex in N_H(θ_Q') adjacent to a non-root vertex of a leaf block of Q'. The proof by contradiction is vacuous when N_H(θ_Q') is empty. That can happen: if the face of G[V2] containing Q has exactly two boundary vertices, the nice-subgraph definition permits H to omit both, so Q has no potential protectors. Nothing in the proof rules this out with 3-connectivity. If Q is never protected, the final application of Lemma 1 cannot colour Q. This is load-bearing for Theorem 4. It may be repairable by strengthening the nice-subgraph lemma or by handling small faces separately, but as written it doesn't go through.\n\nThe contradiction setup also uses a paraphrase that is not the exact negation of the protector rule; it silently assumes Q is non-safe when a potential protector is coloured. This is probably fixable by adding the right invariant, but it needs to be stated and proved.\n\nOne concern the reader raised I disagree with: the claim that in Theorem 5 the contracted vertices can lose degree below s after removing V2 vertices. That's not right, because the removed V2 vertex is adjacent only to the A-vertices in R_i; the survivors keep their degrees. So that particular worry is unfounded.\n\nLemma 4's 'straightforward to verify' step deserves a referee's eye, but I don't see an obvious break there.\n\nBottom line: this paper is for people working on list colouring and DP-colouring. The negative answer is citable now; the upper bound needs a repair. I'd send it to peer review, asking for the protector argument to be completed. It's a serious paper, not a desk reject.","headline":"The counterexample to Richter's question is solid, and the constant-16 theorem is likely true, but the proof of the planar theorem has a gap in the protector argument that needs to be closed.","tokens_in":14502,"tokens_out":13665,"would_cite":true,"duration_ms":141267,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C15","05C10","05C83"],"pacs":[],"model":"deepseek-v4-flash","headline":"A 3-connected planar graph that is not degree-truncated 7-choosable exists, yet every such graph is degree-truncated DP-16-colourable.","keywords":["degree-truncated choosability","DP-colouring","planar graphs","minor-closed families","Gallai trees","GDP-trees","list colouring"],"falsifier":"Check whether the 42-copy graph in Section 2 really has no L-colouring: if any choice of distinct colours for x and y extends to the whole graph, Theorem 6 is false. For the positive half, a single 3-connected non-complete planar graph with a degree-truncated DP-16 cover that admits no colouring would refute Theorem 4.","tokens_in":13312,"feed_emoji":"🎨","tokens_out":10466,"duration_ms":112916,"temperature":0.7,"pith_summary":"Degree-truncated choosability asks whether a graph can be coloured from lists whose sizes are the smaller of a fixed bound and the vertex degree, so low-degree vertices are no longer automatically easy. The paper settles Richter's question: a 3-connected non-complete planar graph is constructed that is not degree-truncated 7-choosable, so the answer is negative even for 7. On the positive side, it proves that every 3-connected non-complete planar graph is degree-truncated DP-16-colourable, hence degree-truncated 16-choosable. The same method applies to every proper minor-closed family: with the appropriate connectivity s, every s-connected member other than a GDP-tree is degree-truncated DP-k-colourable for a constant k depending only on the family.","feed_headline":"Richter's 6-colour hope fails; 16 always works","feed_subtitle":"A new construction blocks 7-colour lists on a 3-connected planar graph, while a universal bound of 16 is proved.","key_machinery":"The engine of the positive proofs is a 'protector' scheme supported by a 'nice subgraph' H of the face-vertex incidence graph Θ(G[V2]) of the high-degree vertices. A nice subgraph is a sparse selection of incidences in which every high-degree vertex is incident to at most two selected faces and every face loses at most two incidences; it guarantees a bounded number of candidate protectors for each low-degree component. When a protector colours itself so that one adjacent low-degree vertex gains a surplus colour, that component becomes 'safe', and Lemma 1, the DP analogue of the Gallai-tree characterization, lets the proof finish it. In the minor-closed setting, the same core idea runs on a K_{s,t}-minor sparsity lemma that orders the high-degree vertices and reserves large private palettes so that final lists stay disjoint on V2.","core_discovery":"The paper establishes that Richter's question has a negative answer and that, despite this, a uniform bounded positive result holds. The negative witness is a 3-connected non-complete planar graph built from 42 copies of a gadget H, with every possible colouring of the two identified vertices x and y blocked in at least one copy. The positive result is proved in the stronger DP-colouring model: for every 3-connected non-complete planar graph and every cover with |L(v)| = min{16, d(v)}, an (L, M)-colouring exists. The proof colours high-degree vertices first, assigns each low-degree GDP-tree component a protector, and then uses the DP analogue of the Gallai-tree characterization to finish the remaining low-degree parts. The same strategy, run on a sparse K_{s,t}-minor lemma, gives the minor-closed family statement.","pith_inferences":["The paper leaves the exact threshold open: since some 3-connected non-complete planar graph fails at 7, the least uniform k for this class is at least 8, and the proof only guarantees k ≤ 16; pinning this number down is a natural next step.","Because the universal bound is proved in the DP model, it is stronger than the list-colouring statement, so any future improvement on the DP side automatically improves the list side.","The protector-and-nice-subgraph scheme is not tied to planarity in an essential way, so the same high-level strategy should apply to any minor-closed family equipped with a sparse K_{s,t}-minor lemma, potentially with much smaller constants than the paper's factorial bound.","One testable consequence of the framework is that the huge constant in Theorem 5 may be an artefact of the proof; whether a polynomial bound in s and t suffices is not addressed in the paper."],"forward_implications":["Richter's original question is closed with a negative answer: the obstruction already appears for 7, hence also for the originally asked 6.","All 3-connected non-complete planar graphs are degree-truncated 16-choosable, so their degree-truncated choice numbers are bounded by 16.","In every proper minor-closed family, the s-connected non-GDP-tree members are degree-truncated DP-k-colourable for a constant k that depends only on the family.","For every fixed surface, all 3-connected non-complete graphs embeddable on that surface are uniformly degree-truncated DP-k-colourable.","The hypotheses are tight: dropping one level of connectivity or allowing complete graphs produces arbitrarily large degree-truncated choice numbers.","A GDP-tree, whose blocks are cliques or cycles, is the only obstruction left in the minor-closed setting, mirroring the Gallai-tree obstruction for ordinary degree-choosability.","The proof implies 16-choosability for every 3-connected non-complete planar graph, so the list-chromatic number in the degree-truncated sense is at most 16 for this class.","The negative construction shows that the universal constant, if it exists for planar graphs, must be at least 8, since a graph not degree-truncated 7-choosable is also not degree-truncated 6-choosable."],"supporting_citations":[{"why":"Provides the DP analogue of the Gallai-tree characterization (Lemma 1), which the proof uses to finish colouring each safe low-degree component.","marker":"[2]"},{"why":"Introduced DP-colouring, the model in which the positive theorems are proved and which makes the protector argument possible.","marker":"[4]"},{"why":"Proved the classical degree-choosability characterization for Gallai-trees, which motivates the GDP-tree exceptions in the minor-closed theorem.","marker":"[5, 10]"},{"why":"Supplies the sparse K_{s,t}-minor edge-counting lemmas that drive the ordering and palette-reservation argument in Theorem 5.","marker":"[9]"}],"fun_headline_variants":["No 7-list for this planar graph; 16 saves every 3-connected case","Richter's conjecture shattered: a planar counterexample resists 7","Universal 16-colour list bound for 3-connected planar graphs","DP-colouring cracks degree-truncated lists: 16 is enough for planar"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof depends on a rescue step: every low-degree part that is a GDP-tree must, at the right moment, receive a protector among the high-degree vertices, adjacent to a cheap non-root vertex of one of its leaf blocks; the written argument does not handle the case where the component's surrounding face has exactly two high-degree boundary vertices and no protector is available.","fun_headline_variants_meta":{"raw":{"variants":["No 7-list for this planar graph; 16 saves every 3-connected case","Richter's conjecture shattered: a planar counterexample resists 7","Universal 16-colour list bound for 3-connected planar graphs","DP-colouring cracks degree-truncated lists: 16 is enough for planar"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001182,"raw_usage":{"total_tokens":4971,"prompt_tokens":1121,"completion_tokens":3850,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":737,"completion_tokens_details":{"reasoning_tokens":3767}},"tokens_in":737,"tokens_out":3850,"duration_ms":29906,"temperature":1.0,"reasoning_tokens":3767,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T17:40:07.597366+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Check whether the 42-copy graph in Section 2 really has no L-colouring: if any choice of distinct colours for x and y extends to the whole graph, Theorem 6 is false. For the positive half, a single 3-connected non-complete planar graph with a degree-truncated DP-16 cover that admits no colouring would refute Theorem 4.","supporting_citations":[{"cited_title":"Bernshteyn, A","cited_arxiv_id":null,"evidence_quote":"Provides the DP analogue of the Gallai-tree characterization (Lemma 1), which the proof uses to finish colouring each safe low-degree component."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduced DP-colouring, the model in which the positive theorems are proved and which makes the protector argument possible."},{"cited_title":"Ossona De Mendez, private communication","cited_arxiv_id":null,"evidence_quote":"Supplies the sparse K_{s,t}-minor edge-counting lemmas that drive the ordering and palette-reservation argument in Theorem 5."}],"review_version":1}