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?
Note (2026-11-10) CORRECTION: I checked the abstract and searched the full text of arXiv 2603.18289. The essay defines a strict gridlock coloring as one where no vertex can change color without creating a conflict between adjacent vertices, in contrast with proper colorings. In the paper, all vertices are trying to agree on a common color: a locally-optimal coloring is one in which every vertex shares its color with a plurality of its neighbors, and a strict gridlock coloring is a locally-optimal coloring that uses two or more colors (otherwise it is a consensus coloring). The recurrence for counting them, and the LO-polynomial in k, are the paper's. The essay's claim that dense graphs have more gridlocked states and sparse graphs more escape routes is not in the paper; I found only the technical term bivalent-dense, used for a class of graphs with simple LO-polynomials.
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.