Back to Search Start Over

Equitable List Vertex Colourability and Arboricity of Grids

Authors :
Drgas-Burchardt, Ewa
Dybizbański, Janusz
Furmańczyk, Hanna
Sidorowicz, Elzbieta
Publication Year :
2018

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 \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 general graphs and for $d$-dimensional grids with $d\geq 5$.<br />Comment: 29 pages, 10 figures

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.1809.08281
Document Type :
Working Paper
Full Text :
https://doi.org/10.2298/FIL1818353D