Choosability and paintability of the lexicographic product of graphs

Abstract

This paper studies the choice number and paint number of the lexicographic product of graphs. We prove that if $G$ has maximum degree $\Delta$, then for any graph $H$ on $n$ vertices $ch(G[H])\le (4\Delta +2)(ch(H)+{\log }_{2}n)$ and ${\chi }_P(G[H])\le (4\Delta +2)({\chi }_P(H)+{\log }_{2}n)$.