Equitable and List Equitable Colorings of Graphs with Bounded Maximum Average Degree

Abstract

A graph is said to be equitably \(k\)-colorable if the vertex set \(V(G)\) can be partitioned into \(k\) independent subsets \(V_1, V_2, \ldots, V_k\) such that \(||V_i| – |V_j|| \leq 1\) (\(1 \leq i, j \leq k\)). A graph \(G\) is equitably \(k\)-choosable if, for any given \(k\)-uniform list assignment \(L\), \(G\) is \(L\)-colorable and each color appears on at most \(\lceil \frac{|V(G)|}{k} \rceil\) vertices. In this paper, we prove that if \(G\) is a graph such that \(\mathrm{mad}(G) \leq 3\), then \(G\) is equitably \(k\)-colorable and equitably \(k\)-choosable where \(k \geq \max\{\Delta(G), 5\}\).