Equitable List Vertex Colourability and Arboricity of Grids

Hanna Furmańczyk, Janusz Dybizbański, Ewa Drgas-Burchardta, El˙zbieta Sidorowicz


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 \geq \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
graphs and for $d$-dimensional grids with $d\geq 5$.


  • There are currently no refbacks.