Pith. sign in

REVIEW 3 minor 12 references

The degree-truncated choice number of 3-connected non-complete planar graphs lies between 10 and 11.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · grok-4.3

2026-06-28 00:26 UTC pith:EOIAF2FM

load-bearing objection This paper tightens the bounds on degree-truncated choice number for 3-connected non-complete planar graphs from 9-12 down to 10-11 via construction plus discharging.

arxiv 2606.06216 v1 pith:EOIAF2FM submitted 2026-06-04 math.CO

Tighter Bounds on the Degree-Truncated Choice Number of Planar Graphs

Huijuan Xu , Huan Zhou , Jialu Zhu , Xuding Zhu This is my paper
classification math.CO MSC 05C15
keywords planar graphschoice numberlist coloringdegree-truncated choosability3-connected graphs
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

This paper proves that the degree-truncated choice number ch^d(P) for the family P of 3-connected non-complete planar graphs satisfies 10 ≤ ch^d(P) ≤ 11. This tightens earlier results showing the value is at least 9 and at most 12. The degree-truncated choice number measures the minimum k where a graph is choosable from lists of size min(k, degree(v)) for each vertex. A reader would care because it refines our understanding of list coloring variants for planar graphs and moves closer to determining the exact value.

Core claim

The paper shows that ch^d(P) is at least 10 because there exist graphs in P requiring 10 colors in this truncated sense, and at most 11 by proving every graph in P is degree-truncated 11-choosable. They conjecture the number equals 10 and verify the conjecture when the subgraph induced by vertices of degree at least 11 is 4-choosable.

What carries the argument

The degree-truncated choice number ch^d(G), defined as the minimum k such that G is f-choosable where f(v) = min{k, d_G(v)}.

Load-bearing premise

The family P of 3-connected non-complete planar graphs admits the stated choosability bounds under the degree-truncated definition f(v) = min{k, d_G(v)}.

What would settle it

A 3-connected non-complete planar graph that is not degree-truncated 11-choosable, or a specific graph in P shown to require 12 under this definition.

Watch this falsifier — get emailed when new claim-graph text bears on it.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 3 minor

Summary. The paper proves that for the family P of 3-connected non-complete planar graphs, the degree-truncated choice number satisfies 10 ≤ ch^d(P) ≤ 11. The lower bound is established by an explicit construction, while the upper bound is obtained via a discharging argument on 3-connected planar graphs. The authors conjecture that equality holds at 10 and confirm the conjecture for the subclass of graphs in P where the subgraph induced by vertices of degree at least 11 is 4-choosable. This improves the prior bounds 9 ≤ ch^d(P) ≤ 12.

Significance. If the bounds hold, the result narrows the possible values of this choosability parameter for planar graphs and brings the problem close to resolution. The combination of an explicit lower-bound construction with a discharging proof for the upper bound, together with the partial confirmation of the conjecture, constitutes a meaningful advance in the study of degree-truncated choosability.

minor comments (3)
  1. [Abstract] Abstract: the reference to the 2025 result of Zhou, Zhu and Zhu would be clearer if the arXiv identifier or full bibliographic details were supplied.
  2. [Introduction] Introduction: the notation ch^d(G) is introduced via the definition of f, but a short illustrative example of a graph that is degree-truncated k-choosable for small k would aid readability.
  3. [Section 4] The statement confirming the conjecture for graphs whose high-degree subgraph is 4-choosable is precise, yet the precise threshold on the minimum degree (11) could be cross-referenced to the discharging rules used in the upper-bound proof.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of our results on the degree-truncated choice number of 3-connected non-complete planar graphs and for recommending minor revision. No major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper establishes tighter bounds 10 ≤ ch^d(P) ≤ 11 via an explicit lower-bound construction on a specific graph family and a discharging-based upper-bound proof for 3-connected planar graphs. These steps rely on standard graph-theoretic definitions of f-choosability and the degree-truncation function, with no fitted parameters, self-definitional reductions, or predictions that collapse to inputs by construction. Prior results (including those with author overlap) are cited only for historical context and are not load-bearing for the new bounds; the central claims are independently derived and self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

No free parameters, invented entities, or non-standard axioms are introduced or fitted in the abstract; the work rests on the standard definitions of choosability, planarity, and 3-connectivity.

axioms (1)
  • standard math Standard definitions and basic properties of planar graphs, 3-connectivity, and list coloring (choosability) from prior literature.
    The abstract invokes these without re-derivation.

pith-pipeline@v0.9.1-grok · 5880 in / 1278 out tokens · 36221 ms · 2026-06-28T00:26:39.017654+00:00 · methodology

0 comments
read the original abstract

Assume $G$ is a graph and $k$ is a positive integer. Let $f:V(G)\to \mathbb{N}$ be defined as $f(v)=\min\{k,d_G(v)\}$. If $G$ is $f$-choosable, then we say $G$ is degree-truncated $k$-choosable. The degree-truncated choice number of $G$ is $\operatorname{ch}^{\text{\st{d}}}(G) = \min\{k: G \text{ is degree-truncated $k$-choosable}\}$. For a family $\mathcal{G}$ of graphs, $\operatorname{ch}^{\text{\st{d}}}(\mathcal{G}) = \max\{\operatorname{ch}^{\text{\st{d}}}(G):G \in \mathcal{G}\}$. Let $\mathcal{P}$ denote the family of 3-connected non-complete planar graphs. Richter asked in 2008 whether $ch^{\text{\st{d}}}(\mathcal{P}) \le 6$. In 2025, Zhou, Zhu and Zhu answered this question in negative and proved that $8 \le ch^{\text{\st{d}}}(\mathcal{P}) \le 16$. This result was improved by Jiang, Xu, Xu, and Zhu, who proved that $9 \le ch^{\text{\st{d}}}(\mathcal{P}) \le 12$. In this paper, we further improve the result and prove that $10 \le \operatorname{ch}^{\text{\st{d}}}(\mathcal{P}) \le 11$. We conjecture that $\operatorname{ch}^{\text{\st{d}}}(\mathcal{P}) =10$, and we confirm this conjecture for those planar graphs $G \in \mathcal{P}$ for which the subgraph induced by vertices of degree at least 11 is 4-choosable.

Figures

Figures reproduced from arXiv: 2606.06216 by Huan Zhou, Huijuan Xu, Jialu Zhu, Xuding Zhu.

Figure 1
Figure 1. Figure 1: The graph H0 and list assignment L0 y2 y1 123567 567 123 c123 123 567 c567 567 567 c567 567 567 c567 567 [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The graph H1 and list assignment L1 z1 4 z2 1234567 123 1234 123 567 4567 567 [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: H2 and list assignment L2 Let graph H1 and list assignment L1, graph H2 and list assignment L2 be given above. It is straightforward to verify that Hi is not Li-colourable. The verification is similar to the case for H0 and L0 and is omitted. Now we take the disjoint union of a copy of H0, two copies of H1 and two copies of H2, combine them as indicated in [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: H′ is not L ′ -colourable (with V (P1) ∩ V (P2) = {x1, x2, x3, y1, y2, y3}). Next we add two vertices u and v to H′ as indicated in [PITH_FULL_IMAGE:figures/full_fig_p005_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: H and list assignment L, each of u and v is adjacent to every vertex "visible" to them, respectively. Let G be a graph obtained from the disjoint union of 72 copies Hi of H by identifying all the copies of v into a single vertex (also named as v) and all the copies of u into a single vertex (also named as u), and adding edges y (i) 3 x (i+1) 3 (where y (i) 3 and x (i) 3 are the copies of y3 and x3 in Hi) f… view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

12 extracted references

  1. [1]

    Coloringsandorientationsofgraphs.Combinatorica, 12(2):125–134, 1992

    NogaAlonandMichaelTarsi. Coloringsandorientationsofgraphs.Combinatorica, 12(2):125–134, 1992

    1992

  2. [2]

    Cranston, Anja Pruchnewski, Zsolt Tuza, and Margit Voigt

    Daniel W. Cranston, Anja Pruchnewski, Zsolt Tuza, and Margit Voigt. List colorings ofK5-minor- free graphs with special list assignments.J. Graph Theory, 71(1):18–30, 2012

    2012

  3. [3]

    Degree-truncated Alon-Tarsi number of outerplanar graphs

    Chenglong Deng and Xuding Zhu. Degree-truncated Alon-Tarsi number of outerplanar graphs. Discrete Appl. Math., 386:175–183, 2026

    2026

  4. [4]

    Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8.J

    Zdeněk Dvořák and Luke Postle. Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8.J. Combin. Theory Ser. B, 129:38–54, 2018

    2018

  5. [5]

    Rubin, and Herbert Taylor

    Paul Erdős, Arthur L. Rubin, and Herbert Taylor. Choosability in graphs. InProceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing (Humboldt State Univ., Arcata, Calif., 1979), volume XXVI ofCongress. Numer., pages 125–157. Utilitas Math., Winnipeg, MB, 1980

    1979

  6. [6]

    Hutchinson

    Joan P. Hutchinson. On list-coloring outerplanar graphs.J. Graph Theory, 59(1):59–74, 2008

    2008

  7. [7]

    Degree-truncated choice number of planar graphs.Discrete Math., 349(7):Paper No

    Yiting Jiang, Huijuan Xu, Xinbo Xu, and Xuding Zhu. Degree-truncated choice number of planar graphs.Discrete Math., 349(7):Paper No. 115035, 15, 2026

    2026

  8. [8]

    Degree-truncated DP- colourability ofK 2,4-minor-free graphs.European J

    On-Hei Solomon Lo, Cheng Wang, Huan Zhou, and Xuding Zhu. Degree-truncated DP- colourability ofK 2,4-minor-free graphs.European J. Combin., 133:Paper No. 104306, 25, 2026

    2026

  9. [9]

    Every planar graph is5-choosable.J

    Carsten Thomassen. Every planar graph is5-choosable.J. Combin. Theory Ser. B, 62(1):180–181, 1994

    1994

  10. [10]

    V. G. Vizing. Coloring the vertices of a graph in prescribed colors.Diskret. Analiz, (29):3–10, 101, 1976

    1976

  11. [11]

    List colourings of planar graphs.Discrete Math., 120(1-3):215–219, 1993

    Margit Voigt. List colourings of planar graphs.Discrete Math., 120(1-3):215–219, 1993

    1993

  12. [12]

    Degree-truncated choosability of graphs.J

    Huan Zhou, Jialu Zhu, and Xuding Zhu. Degree-truncated choosability of graphs.J. Combin. Theory Ser. B, 175:171–186, 2025. 15

    2025