The q-Coloring problem asks whether the vertices of a graph can be properly colored with q colors. In this paper we perform a fine-grained analysis of the complexity of q- Coloring with respect to a hierarchy of structural ...