Colorings with few Colors: Counting, Enumeration and Combinatorial Bounds
Edge coloring, total coloring and L(2,1)-labeling are well-studied NP-hard graph problems. Even the versions asking whether a graph has a coloring with few colors or a labeling with few labels remain NP-hard on graphs of small maximum degree.
coloring counting enumeration graphs algorithms exact exponential time algorithms