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

h o_{l}^{=} (G)

. Zhang in 2016 posed the conjecture that if

k g e q l c e i l (D e l t a (G) + 1) / 2 c e i l

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 i n 2, 3, 4

and give new bounds on

h o_{l}^{=} (G)

for general graphs and for

d

-dimensional grids with

d g e q 5

.

Recommendations

Cites Work

Cited In (10)

This page was built for publication: Equitable list vertex colourability and arboricity of grids