Back to Search
Start Over
Equitable List Vertex Colourability and Arboricity of Grids
- 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
- Subjects :
- Mathematics - Combinatorics
05C15, 05C76
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.1809.08281
- Document Type :
- Working Paper
- Full Text :
- https://doi.org/10.2298/FIL1818353D