Pith. sign in

REVIEW 3 major objections 3 minor 24 references

Degree-truncated choosability of graphs

T0 review · 3 major / 3 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A 3-connected planar graph that is not degree-truncated 7-choosable exists, yet every such graph is degree-truncated DP-16-colourable.

desk verdict 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. read the letter →

arxiv 2507.10453 v1 pith:OSFKKX4T submitted 2025-07-14 math.CO

Huan Zhou , Jialu Zhu , Xuding Zhu This is my paper · ORCID
classification math.CO MSC 05C1505C1005C83
keywords degree-truncatedchoosabilityDP-colouringplanargraphsminor-closedfamiliesGallaitreesGDP-treeslistcolouring
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 3 minor

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]).

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 (3)
  1. [Section 3, Lemma 3] 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.
  2. [Section 3, Lemma 3, path argument] 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.
  3. [Section 3, protector assignment rule] 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.
minor comments (3)
  1. [Abstract and Section 1, Theorems 3 and 5] 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.
  2. [Definition 7] 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.
  3. [Section 2, Theorem 6] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the main proofs are self-contained and the only same-author citation is motivational.

full rationale

The derivation chain for Theorems 4 and 5 is self-contained. Theorem 4 is proved from Lemma 1, an external DP-GDP-tree characterization from Bernshteyn-Kostochka-Pron [2]; from Lemma 2, which is proved here by induction in Section 4; and from an explicit protector-assignment argument whose constants (16, costs at most 5) are derived, not fitted. The self-citation [7] (Lo, Wang, Zhou, Zhu) appears only as historical context about K_{2,4}-minor-free graphs and is not used to justify any theorem in this paper. Theorem 5 uses only external minor-density bounds of Thomason [9] and the same Lemma 1; the constants q and k are chosen explicitly. The negative result Theorem 6 is a self-contained construction. No equation or parameter is defined in terms of the statement it is used to prove, and no prediction is a renamed fitted input. One could question whether Lemma 3's proof covers the degenerate case N_H(theta_Q') = empty, but that would be a correctness gap in the proof, not a circularity, and it does not change the circularity score.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The paper introduces no fitted parameters and no invented entities. The central claims rest on two external pillars: the GDP-tree classification of tight DP-degree-colouring (Lemma 1, from Bernshteyn-Kostochka-Pron [2]) and Thomason's K_{s,t}-minor density estimates (Lemmas 5 and 6, from [9]), plus standard planar graph facts (5-degeneracy, Euler bounds, Menger-type path arguments in 3-connected plane graphs). The in-paper nice-subgraph lemma (Lemmas 2 and 4) is proved by induction but contains a deferred 'straightforward to verify' step.

assumptions (5)
  • domain assumption GDP-tree classification of tight DP-degree-colouring (Lemma 1 from [2])
    External theorem of Bernshteyn, Kostochka, Pron: if f(v) >= d_G(v) for all v, then G is DP-f-colourable unless f = d_G pointwise and G is a GDP-tree. Used at the end of Sections 3 and 5 to color remaining safe V1 components.
  • domain assumption Thomason's K_{s,t}-minor density estimates (Lemmas 5 and 6 from [9])
    External results bounding edges per vertex in K_{s,t}-minor-free graphs; used in Section 5 to construct the ordering of V2 and the partition into R_i sets.
  • standard math Planar graphs are 5-degenerate, and plane graphs satisfy Euler face bounds
    Section 3 uses a V2 ordering with at most 5 earlier neighbors and the visible-face reduction (A1, A2).
  • standard math Menger/connectivity facts for 3-connected plane graphs (path separation arguments, no small separators)
    Used in Lemma 3's path argument and in the A2 edge-adding step; the authors note 3-connectedness is needed for (A2).
  • standard math The complete bipartite sharpness construction K_{s-1,k^{s-1}} is not degree-truncated k-choosable
    Introduction's necessity example with lists L(v_i) = [k] x {i}; standard obstruction, verified by the displayed list assignment.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Degree-truncated choosability of graphs." pith.science (2026). https://pith.science/paper/OSFKKX4T

@misc{pith2026250710453,
  author       = {Pith},
  title        = {Pith review of: Degree-truncated choosability of graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/OSFKKX4T}},
  note         = {Machine review of arXiv:2507.10453}
}
abstract

A graph $G$ is called degree-truncated $k$-choosable if for every list assignment $L$ with $|L(v)| \ge \min\{d_G(v), k\}$ for each vertex $v$, $G$ is $L$-colourable. Richter asked whether every 3-connected non-complete planar graph is degree-truncated 6-choosable. We answer this question in negative by constructing a 3-connected non-complete planar graph which is not degree-truncated 7-choosable. Then we prove that every 3-connected non-complete planar graph is degree-truncated 16-DP-colourable (and hence degree-truncated $16$-choosable). We further prove that for an arbitrary proper minor closed family ${\mathcal G}$ of graphs, let $s$ be the minimum integer such that $K_{s,t} \notin \mathcal{G}$ for some $t$, then there is a constant $k$ such that every $s$-connected graph $G \in {\mathcal G}$ other than a GDP tree is degree-truncated DP-$k$-colourable (and hence degree-truncated $k$-choosable), where a GDP-tree is a graph whose blocks are complete graphs or cycles. In particular, for any surface $\Sigma$, there is a constant $k$ such that every 3-connected non-complete graph embeddable on $\Sigma$ is degree-truncated DP-$k$-colourable (and hence degree-truncated $k$-choosable). The $s$-connectedness for graphs in $\mathcal{G}$ (and 3-connectedness for graphs embeddable on $\Sigma$) is necessary, as for any positive integer $k$, $K_{s-1,k^{s-1}} \in \mathcal{G}$ ($K_{2,k^2}$ is planar) is not degree-truncated $k$-choosable. Also, non-completeness is a necessary condition, as complete graphs are not degree-choosable.

Figures

Figures reproduced from arXiv: 2507.10453 by the authors.

Figure 1
Figure 1. The graph H Theorem 5. For any proper minor closed family G of graphs, there is a constant k such that every s-connected graph in G other than a GDP-tree is degree-truncated DP-k-colourable, where s is the smallest integer such that Ks,t ∈ G / for some positive integer t. In particular, for any fixed surface Σ, there is a constant k such that every 3-connected non-complete graph embedded in Σ is degree-truncated DP-… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

24 extracted references · 23 canonical work pages

  1. [1]

    Bernshteyn

    A. Bernshteyn. The asymptotic behavior of the correspondence chromatic number, Discrete Math., 339 (11) (2016), 2680–2692 (cit. on p. 4)

    work page 2016

  2. [2]

    Bernshteyn, A

    A. Bernshteyn, A. Kostochka and S. Pron. On DP-coloring of graphs and multigraphs, Sibirsk. Mat. Zh.58 (2017), no.1, 36-47; translation in Sib. Math. J.58 (2017), no.1, 28-36

    work page 2017

  3. [3]

    Cranston, A

    D. Cranston, A. Pruchnewski, Z. Tuza and M. Voigt, List colorings of K_5 -minor-free graphs with special list assignments , J. Graph Theory 71 (2012), 18-30

    work page 2012

  4. [4]

    T. Dai, J. Hu, H. Li, and S. Maezawa. On DP-coloring of outerplanar graphs, Manuscript, 2023

    work page 2023

  5. [5]

    Dvo r \' a k and L

    Z. Dvo r \' a k and L. Postle, Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8, J. Combin. Theory Ser. B 129 (2018) 38-54

    work page 2018

  6. [6]

    Erd o s, A.L

    P. Erd o s, A.L. Rubin, H. Taylor, Choosability in graphs, in: Proc. West Coast Conf. on Combinatorics, Graph Theory and Computing, Congressus Numerantium XXVI, 1979, pp. 125-157

    work page 1979

  7. [7]

    Hutchinson, On list-Coloring outerplanar graphs , J

    J. Hutchinson, On list-Coloring outerplanar graphs , J. Graph Theory 59 (2008), 59-74

    work page 2008

  8. [8]

    O. S. Lo, C. Wang, H. Zhou and X. Zhu, K_ 2,4 -minor free graphs are DP-5-truncated degree-colourable , arXiv:2312.15962

    work page Pith review arXiv

Show all 24 references
  1. [9]

    Ossona De Mendez, private communication

    P. Ossona De Mendez, private communication

  2. [10]

    Stiebitz and M

    M. Stiebitz and M. Voigt, List-colourings , Topics in chromatic graph theory, 114–136. Encyclopedia Math. Appl., 156

  3. [11]

    Thomason, Disjoint complete minors and bipartite minors , European J

    A. Thomason, Disjoint complete minors and bipartite minors , European J. Combin. 28 (2007) 1779-1783

    2007

  4. [12]

    Vizing, Coloring the vertices of a graph in prescribed colors, Diskret

    V.G. Vizing, Coloring the vertices of a graph in prescribed colors, Diskret. Analiz 29 Metody Diskret. Anal. v Teorii Kodov i Shem (1976) 3-10, p. 101, (in Russian)

    1976

  5. [13]

    Alon and M

    N. Alon and M. Tarsi, Colorings and orientations of graphs , Combinatorica, 12(2) (1992), 125-134

    1992

  6. [14]

    Bernshteyn and E

    A. Bernshteyn and E. Lee, Weak degeneracy of graphs , J. Graph Theory 103 (2023), no.4, 607-634

    2023

  7. [15]

    Bernshteyn, E

    A. Bernshteyn, E. Lee and E. Smith-Roberge Weak Degeneracy of Planar Graphs , arxiv: 2406.02792

    arXiv

  8. [16]

    Bradshaw and A

    P. Bradshaw and A. Zeng, DP-paintability and deletion scheme, manuscript, 2023

    2023

  9. [17]

    DeVos, K.-I

    M. DeVos, K.-I. Kawarabayashi, B. Mohar, Locally planar graphs are 5-choosable, J. Combin. Theory Ser. B 98 (2008) 215-1232

    2008

  10. [18]

    M. Han, J. He and X. Zhu, Weak degeneracy of the square of line graphs, Adv. Math. (China), 2023

    2023

  11. [19]

    M. Han, T. Wang, J. Wu, H. Zhou and X. Zhu, Weak degeneracy of planar graphs and locally planar graphs , Electron. J. Combin. 30 (2023), no.4, Paper No. 4.18

    2023

  12. [20]

    S.-J. Kim, A. V. Kostochka, X. Li and X. Zhu, On-line DP -coloring of graphs , Discrete Appl. Math. 285 (2020) 443--453

    2020

  13. [21]

    Kozik and B

    J. Kozik and B. Podkanowicz, Schnyder Woods and Alon-Tarsi number of planar graphs , Electron. J. Combin. 31 (2024), no. 1, Paper No. 1.59

    2024

  14. [22]

    Schauz, Mr

    U. Schauz, Mr. Paint and Mrs. Correct, Electron. J. Combin.16 (2009), no.1, Research Paper 77, 18 pp

    2009

  15. [23]

    Yang, Weak degeneracy of regular graphs, arxiv: 2309.12670

    Y. Yang, Weak degeneracy of regular graphs, arxiv: 2309.12670

    arXiv

  16. [24]

    Zhu, Online list colouring of graphs, Electron

    X. Zhu, Online list colouring of graphs, Electron. J. Combin. 16 (1) (2009) 16, Research Paper 127

    2009

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.