{"id":"arxiv/2603.23379","url":"https://arxiv.org/abs/2603.23379","tags":["math.CO"],"score":0,"title":"Frugal colourings of graphs via sparse hypergraph colouring","domain":"math.CO","source":"arxiv","authors":["Quentin Chuet"],"reviews":0,"subject":"math.CO","summary":"A proper colouring of a graph $G$ is $β$-frugal if every colour appears at most $β$ times in the neighbourhood of each vertex. Let $χ_β(G)$ denote the minimum number of colours required for a $β$-frugal colouring of $G$. For a fixed frugality $β$, Hind et al. showed that $χ_β(G) = \\mathcal{O}(Δ(G)^{1 + 1/β})$, and a bipartite construction of Alon certifies the tightness of this upper bound up to a constant factor. Using a sparse hypergraph colouring theorem of Li and Postle, we show that for all fixed $β\\ge 2$ and $t\\ge 2$, if $G$ excludes either $C_{2t}$ or $K_{β,t}$ as a subgraph, then…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-03-24","reactions":{}}