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

Source 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.$$