Degree-truncated DP-colouring of {K_4,K_2,t}-minor-free graphs

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₄,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₄-minor remains excluded. A bound independent of t is impossible, as shown by the family {K_2,n| n≥ 2}. Let 𝒮_t be the class of $2$-connected {K₄,K_2,t}-minor-free graphs other than cycles. Writing χ^soutd_DP(𝒮_t) for the least truncation threshold valid throughout this class, we prove that, for every integer t≥3, ⌊2√(2t)⌋ ≤ χ^soutd_DP(𝒮_t) ≤ ⌈4√(2t)⌉.

Degreewise Cut-Semigroup Saturation for K₅-Minor-Free Graphs and Seymour's Planar Edge-Colouring Conjecture
SeungJu Lee
arXiv11 Sep 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
On the maximum degree and order of K_t-minor-free graphs with positive Lin--Lu--Yau curvature
Zi-Xia Song
arXiv22 Oct 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
Obstructions to k-colouring H-free graphs
Iain Beaton, Ben Cameron, Adam van Omme
arXiv7 Oct 2026PreprintCC BY-NC-SA 4.0Full textCombinatorics & discrete mathematicsarXiv
Four colours are needed for closed-neighbourhood conflict-free colouring of all planar graphs
Jelena Sedlar, Riste Škrekovsk
arXiv15 Oct 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
Coloring Small K_t-Minor-Free Graphs
Xinheng Lin
arXiv8 Sep 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeX RIS

BibTeX

@misc{zhou2026degreetruncated,
  title = {{Degree-truncated DP-colouring of $\K_4,K_2,t\$-minor-free graphs}},
  author = {Huan Zhou},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.36586},
  eprint = {2610.36586},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.36586},
  note = {CC BY-SA 4.0},
}

RIS

TY  - UNPB
TI  - Degree-truncated DP-colouring of {K_4,K_2,t}-minor-free graphs
AU  - Huan Zhou
PY  - 2026
DA  - 2026/10/27
PB  - arXiv
DO  - 10.48550/arxiv.2610.36586
UR  - https://arxiv.org/abs/2610.36586
AB  - 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≥ 2}. Let 𝒮_t be the class of $2$-connected {K_4,K_2,t}-minor-free graphs other than cycles. Writing χ^soutd_DP(𝒮_t) for the least truncation threshold valid throughout this class, we prove that, for every integer t≥3, ⌊2√(2t)⌋ ≤ χ^soutd_DP(𝒮_t) ≤ ⌈4√(2t)⌉.
ER  -

Degree-truncated DP-colouring of {K₄,K_2,t}-minor-free graphs

Abstract

Related

Cite