Degree-truncated DP-colouring of K 4,K 2,t-minor-free graphs
math.CO
Submitted: 2026-10-27
Updated: 2026-10-27
Comments: 17 pages 3 figures
License: http://creativecommons.org/licenses/by-sa/4.0/
The gist: 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)= k,d G(v) for every vertex v.
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)= 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 at least 2. Let S t be the class of 2-connected K 4,K 2,t-minor-free graphs other than cycles. Writing χ DP(S t) for the least truncation threshold valid throughout this class, we prove that, for every integer t at least3, 2 sqrt 2t at most χ DP(S t) at most 4 sqrt 2t.
Related papers
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality