Frugal colourings of graphs via sparse hypergraph colouring

Abstract

A proper colouring of a graph $G$ is $\beta$-frugal if every colour appears at most $\beta$ times in the neighbourhood of each vertex. Let ${\chi }_{\beta }(G)$ denote the minimum number of colours required for a $\beta$-frugal colouring of $G$. For a fixed frugality $\beta$, Hind et al. showed that ${\chi }_{\beta }(G)=\mathcal{O}(\Delta (G{)}^{1+1/\beta })$, 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 $\beta \ge 2$ and $t\ge 2$, if $G$ excludes either $C_{2t}$ or $K_{\beta ,t}$ as a subgraph, then ${\chi }_{\beta }(G)=\mathcal{O}(\Delta (G{)}^{1+1/\beta }/(\log \Delta (G){)}^{1/\beta })$. Furthermore, we show that these upper bounds are tight up to a constant factor due to the existence of graphs $G$ with arbitrarily large maximum degree $\Delta$ and girth such that ${\chi }_{\beta }(G)=\Omega ({\Delta }^{1+1/\beta }/(\log \Delta {)}^{1/\beta })$. Finally, we show that excluding an arbitrary bipartite subgraph does not necessarily reduce the order of growth of ${\chi }_{\beta }$, as there exist $K_{4^{\beta +1},4^{\beta +1}}$-free graphs $G$ with arbitrarily large maximum degree $\Delta$ such that ${\chi }_{\beta }(G)=\Omega ({\Delta }^{1+1/\beta })$.

arXiv commentAdded Theorem 12, which shows that excluding an arbitrary bipartite subgraph does not necessarily reduce the order of growth of ${\chi }_{\beta }$. Added statement on AI use. Various minor adjustments and corrections