Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2603.23379 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910077528571904 |
|---|---|
| author | Chuet, Quentin |
| author_facet | Chuet, Quentin |
| contents | 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 needed for a $β$-frugal colouring of $G$. For a fixed value of $β$, Hind et al. showed that $χ_β(G) = \mathcal{O}(Δ(G)^{1 + 1/β})$, and a construction of Alon certifies the tightness of this upper bound up to a constant factor. We show that, for all fixed $β\ge 2$ and $t\ge 2$, if $G$ does not contain $C_{2t}$ as a subgraph, or if $G$ does not contain $K_{β,t}$ as a subgraph, then $χ_β(G) = \mathcal{O}(Δ(G)^{1 + 1/β} / (\logΔ(G))^{1/β})$. Furthermore, we show that these upper bounds are tight up a constant factor due to the existence of graphs $G$ with arbitrarily large maximum degree $Δ$ and girth such that $χ_β(G) = Ω(Δ^{1 + 1/β} / (\logΔ)^{1/β})$. The upper bounds are obtained via a sparse hypergraph colouring theorem of Li and Postle. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_23379 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Frugal colourings of graphs via sparse hypergraph colouring Chuet, Quentin Combinatorics 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 needed for a $β$-frugal colouring of $G$. For a fixed value of $β$, Hind et al. showed that $χ_β(G) = \mathcal{O}(Δ(G)^{1 + 1/β})$, and a construction of Alon certifies the tightness of this upper bound up to a constant factor. We show that, for all fixed $β\ge 2$ and $t\ge 2$, if $G$ does not contain $C_{2t}$ as a subgraph, or if $G$ does not contain $K_{β,t}$ as a subgraph, then $χ_β(G) = \mathcal{O}(Δ(G)^{1 + 1/β} / (\logΔ(G))^{1/β})$. Furthermore, we show that these upper bounds are tight up a constant factor due to the existence of graphs $G$ with arbitrarily large maximum degree $Δ$ and girth such that $χ_β(G) = Ω(Δ^{1 + 1/β} / (\logΔ)^{1/β})$. The upper bounds are obtained via a sparse hypergraph colouring theorem of Li and Postle. |
| title | Frugal colourings of graphs via sparse hypergraph colouring |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2603.23379 |