Equitable tree colouring of graphs

Abstract

Let $k\in \mathbb{N}$ and let $G$ be a simple graph with maximum degree $\hat{I}”$. A $k$-colouring $\ddot{I}†$ of $G$ is an assignment of colours from $\{1,2,\dots ,k\}$ to the vertices of $G$. We call $\ddot{I}†$ 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 \hat{I}”+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\hat{I}{”}^4$ and $k\ge (\hat{I}”+2)/2$, then every $n$-vertex graph with maximum degree at most $\hat{I}”$ contains an equitable tree $k$-colouring. This confirms a conjecture of Wu, Zhang, and Li when $\hat{I}”$ 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.

15 pages