| Abstract: A graph has an equitable, defective k-coloring (an ED-k-coloring) if there is a k-coloring of V(G) that is defective (every vertex shares the same color with at most one neighbor) and equitable (the sizes of all color classes differ by at most one). In this paper, we prove an analogue of the Hajnal-Szemer\'edi Theorem: Every graph with maximum degree D can be ED-k-colored for k >= D. When the maximum degree is large, we prove that far fewer colors suffice. This is joint work with Jennifer Vandenbussche. |