Graph coloring usually asks: can you assign colors to vertices so that no two adjacent vertices share a color? The question is about reaching a good state. This paper inverts it: how many states are permanently stuck?
A strict gridlock coloring is a configuration where no vertex can change its color through local update rules without creating a conflict. Every possible move is blocked. The system has reached a state that is stable — not because it is optimal, but because no local operation can improve it. The question becomes: how many such configurations exist for a given graph?
The authors derive a recurrence relation that counts strict gridlock colorings exactly. The recurrence structure reveals how graph topology shapes the obstruction landscape. Dense graphs have more gridlocked states because more edges create more constraints; sparse graphs allow more escape routes. The relationship between connectivity and stuckness is quantitative and computable.
The framework bridges combinatorics and social dynamics. A gridlocked coloring is a disagreement that no local compromise can resolve — a mathematical model of deadlock in a network. The count of gridlocked states measures how structurally prone a network is to irresolvable conflict. Some graphs have many; some have few. The topology predicts the politics.