Equitable List Vertex Colourability and Arboricity of Grids

Abstract

A graph $G$ is equitably $k$-list arborable if for any $k$-uniform list assignment $L$, there is an equitable $L$-colouring of $G$ whose each colour class induces an acyclic graph. The smallest number $k$ admitting such a coloring is named equitable list vertex arboricity and is denoted by ${\rho }_l^{=}(G)$. Zhang in 2016 posed the conjecture that if $k\ge \lceil (\Delta (G)+1)/2\rceil$ then $G$ is equitably $k$-list arborable. We give some new tools that are helpful in determining values of $k$ for which a general graph is equitably $k$-list arborable. We use them to prove the Zhang's conjecture for $d$-dimensional grids where $d\in \{2,3,4\}$ and give new bounds on ${\rho }_l^{=}(G)$ for general graphs and for $d$-dimensional grids with $d\ge 5$.

29 pages, 10 figures