Equitable tree colouring of graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911594753032192 |
|---|---|
| author | Gao, Yuping Lo, Allan Shan, Songling |
| author_facet | Gao, Yuping Lo, Allan Shan, Songling |
| contents | Let $k \in \mathbb{N}$ and let $G$ be a simple graph with maximum degree $Δ$. A $k$-colouring $φ$ of $G$ is an assignment of colours from $\{1,2,\ldots,k\}$ to the vertices of $G$. We call $φ$ proper if adjacent vertices receive distinct colours, and equitable if the sizes of any two colour classes differ by at most one. The celebrated Hajnal--Szemerédi theorem states that a proper equitable $k$-colouring exists whenever $k \ge Δ+ 1$.
In this paper, we study its tree colouring variant in which each colour class induces a forest. This is closely related to the vertex arboricity which was introduced by Chartrand, Kronk, and Wall. More precisely, we prove that if $n \ge 3Δ^4$ and $k \ge (Δ+2)/2$, then every $n$-vertex graph with maximum degree at most $Δ$ contains an equitable tree $k$-colouring. This confirms a conjecture of Wu, Zhang, and Li when $Δ$ is even and up to an additive constant of $1$ otherwise for large $n$. We also consider $d$-degenerate colouring in which each colour class induces a $d$-degenerate graph. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_13606 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Equitable tree colouring of graphs Gao, Yuping Lo, Allan Shan, Songling Combinatorics Let $k \in \mathbb{N}$ and let $G$ be a simple graph with maximum degree $Δ$. A $k$-colouring $φ$ of $G$ is an assignment of colours from $\{1,2,\ldots,k\}$ to the vertices of $G$. We call $φ$ proper if adjacent vertices receive distinct colours, and equitable if the sizes of any two colour classes differ by at most one. The celebrated Hajnal--Szemerédi theorem states that a proper equitable $k$-colouring exists whenever $k \ge Δ+ 1$. In this paper, we study its tree colouring variant in which each colour class induces a forest. This is closely related to the vertex arboricity which was introduced by Chartrand, Kronk, and Wall. More precisely, we prove that if $n \ge 3Δ^4$ and $k \ge (Δ+2)/2$, then every $n$-vertex graph with maximum degree at most $Δ$ contains an equitable tree $k$-colouring. This confirms a conjecture of Wu, Zhang, and Li when $Δ$ is even and up to an additive constant of $1$ otherwise for large $n$. We also consider $d$-degenerate colouring in which each colour class induces a $d$-degenerate graph. |
| title | Equitable tree colouring of graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2604.13606 |