Exponential time complexity describes algorithms whose running time grows exponentially with input size. General algorithms for graph coloring are exponential because no polynomial-time solution is known. section 8.7
Backtracking exposes the trade-off clearly: it guesses every possible color for a selected node, recurses, and rejects partial assignments that violate constraints. A reducer can avoid enumerating some impossible branches, but the worst-case search remains exponential. section 8.7
Graph coloring
Color each graph node by repeatedly selecting a node, trying all possible colors, and classifying the result as broken, complete, or partial. The partial cases continue recursively; constraint-based reduction makes practical instances manageable without changing the general complexity class. section 8.7
