Degree-truncated DP-colouring of $\{K_4,K_{2,t}\}$-minor-free graphs

A graph $G$ is degree-truncated DP-$k$-colourable (respectively, degree-truncated $k$-choosable) if it is DP-$f$-colourable (respectively, $f$-choosable), where $f(v)=\min\{k,d_G(v)\}$ for every vertex $v$. Hutchinson proved that every $2$-connected maximal outerplanar graph other than the triangle is degree-truncated $5$-choosable. Lo, Wang, Zhou and Zhu strengthened this result by proving that every $2$-connected $K_{2,4}$-minor-free graph other than cycles and complete graphs is degree-truncated DP-$5$-colourable. Outerplanar graphs are precisely the $\{K_4,K_{2,3}\}$-minor-free graphs. We study how the truncation threshold grows when $K_{2,3}$ is replaced by $K_{2,t}$, while $K_4$-minor remains excluded. A bound independent of $t$ is impossible, as shown by the family $\{K_{2,n}| n\ge 2\}$. Let $\mathcal S_t$ be the class of $2$-connected $\{K_4,K_{2,t}\}$-minor-free graphs other than cycles. Writing $χ^{\text{\sout{d}}}_{\mathrm{DP}}(\mathcal S_t)$ for the least truncation threshold valid throughout this class, we prove that, for every integer $t\ge3$, \[ \left\lfloor2\sqrt{2t}\right\rfloor \le χ^{\text{\sout{d}}}_{\mathrm{DP}}(\mathcal S_t) \le \left\lceil4\sqrt{2t}\right\rceil. \]

Authors

Publication Details

Journal
arXiv (Cornell University)
Published
2026-10-27
DOI
https://doi.org/10.48550/arxiv.2610.36586
Primary Topic
Advanced Graph Theory Research
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
preprint

Degree-truncated DP-colouring of $\{K_4,K_{2,t}\}$-minor-free graphs

Huan Zhou
arXiv (Cornell University)
Advanced Graph Theory Research
preprint

Degree-truncated DP-colouring of $\{K_4,K_{2,t}\}$-minor-free graphs

Huan Zhou
preprint en

Abstract

A graph $G$ is degree-truncated DP-$k$-colourable (respectively, degree-truncated $k$-choosable) if it is DP-$f$-colourable (respectively, $f$-choosable), where $f(v)=\min\{k,d_G(v)\}$ for every vertex $v$. Hutchinson proved that every $2$-connected maximal outerplanar graph other than the triangle is degree-truncated $5$-choosable. Lo, Wang, Zhou and Zhu strengthened this result by proving that every $2$-connected $K_{2,4}$-minor-free graph other than cycles and complete graphs is degree-truncated DP-$5$-colourable. Outerplanar graphs are precisely the $\{K_4,K_{2,3}\}$-minor-free graphs. We study how the truncation threshold grows when $K_{2,3}$ is replaced by $K_{2,t}$, while $K_4$-minor remains excluded. A bound independent of $t$ is impossible, as shown by the family $\{K_{2,n}| n\ge 2\}$. Let $\mathcal S_t$ be the class of $2$-connected $\{K_4,K_{2,t}\}$-minor-free graphs other than cycles. Writing $χ^{\text{\sout{d}}}_{\mathrm{DP}}(\mathcal S_t)$ for the least truncation threshold valid throughout this class, we prove that, for every integer $t\ge3$, \[ \left\lfloor2\sqrt{2t}\right\rfloor \le χ^{\text{\sout{d}}}_{\mathrm{DP}}(\mathcal S_t) \le \left\lceil4\sqrt{2t}\right\rceil. \]

arXiv (Cornell University)
Advanced Graph Theory Research
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon
Degree-truncated DP-colouring of $\{K_4,K_{2,t}\}$-minor-free graphs — Huan Zhou · arXiv (Cornell University) (2026) | TGRS Research Map | TGRS