Grundy Number¶
The largest number of colors that first-fit vertex coloring can be forced to use over all vertex orderings measures a graph's worst-case greedy order sensitivity.
Core Idea¶
The Grundy number \(\Gamma(G)\), also called the Grundy chromatic number, is the maximum number of colors that the first-fit greedy vertex-coloring algorithm can use on a graph \(G\) as the vertex ordering ranges over all possibilities. First-fit processes vertices sequentially and assigns each the smallest positive color absent from its already colored neighbors. The Grundy number therefore measures the worst ordering sensitivity of this locally reasonable coloring rule.
Equivalently, a proper coloring is a Grundy \(k\)-coloring when every vertex of color \(j\) has a neighbor in every color \(i<j\); \(\Gamma(G)\) is the largest \(k\) admitting such a coloring. Christen and Selkow introduced this graph-coloring invariant and its defining lower-color-neighbor condition. Zaker develops the same definition, complexity, bounds, and well-colored-graph consequences.
Scope of Application¶
Grundy number belongs to structural and algorithmic graph theory. It organizes worst-case analysis of greedy coloring, recognition of order-robust graph classes, parameterized algorithms, approximation hardness, and bounds for trees, chordal graphs, bipartite graphs, complements, and sparse classes.
Zaker shows that deciding whether \(\Gamma(G)\geq k\) is polynomial for fixed \(k\), while general computation is NP-complete, and defines well-colored graphs by \(\Gamma(G)=\chi(G)\). Later complexity work distinguishes Grundy Coloring from weak and connected variants and maps fixed-parameter behavior across graph classes.
Clarity¶
The lower-color witness condition explains why the ordering and coloring definitions agree. If first-fit assigns color \(j\), colors \(1,\ldots,j-1\) must already appear among the vertex's neighbors. Conversely, order the color classes from low to high; every vertex of color \(j\) then sees witnesses of all lower colors and first-fit assigns \(j\).
Manages Complexity¶
The invariant compresses an exponentially large ordering space into one number while retaining a witness coloring. It makes graph families comparable by how badly local greedy decisions can be manipulated by order.
That compression directs algorithm design. A small Grundy number gives an order-independent ceiling for first-fit. Equality \(\Gamma=\chi\) says every first-fit outcome is optimal in color count.
Abstract Reasoning¶
Because any first-fit result is a proper coloring, it uses at least \(\chi(G)\) colors. Because a color-\(j\) vertex has degree at least \(j-1\), it uses at most \(\Delta(G)+1\). These yield
Subgraph monotonicity requires qualification. If \(H\) is an induced subgraph of \(G\), any Grundy coloring of \(H\) remains realizable in \(G\) after placing the other vertices later only if their effects do not alter earlier assignments; ordering the vertices of \(H\) first proves \(\Gamma(H)\leq\Gamma(G)\).
Knowledge Transfer¶
The invariant transfers literally among graph classes and applications that retain proper vertex coloring plus first-fit order. Paths, trees, bipartite graphs, interval graphs, and conflict graphs share the same recognition rule.
The broader pattern—measure worst-case sensitivity of a greedy algorithm to presentation order—transfers to other algorithms, but that pattern belongs to Greedy Algorithm and adversarial-order reasoning. Their performance measures are not Grundy numbers unless colors and lower-color witnesses remain literal.
Relationships to Other Abstractions¶
Current abstraction Grundy Number Domain-specific
Parents (1) — more general patterns this builds on
-
Grundy Number presupposes Graph Coloring Prime
Grundy Number presupposes prime:graph_coloring because every first-fit outcome is a proper vertex coloring and the invariant compares against chromatic structure.
Hierarchy path (1) — routes to 1 parentless root
- Grundy Number → Graph Coloring → Partition → Set and Membership
Neighborhood in Abstraction Space¶
Grundy Number sits in a sparse region of the domain-specific corpus (76th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Graph Coloring Games & Drawings (7 abstractions)
Nearest neighbors
- Probabilistic Graphical Model — 0.84
- Greedy coloring — 0.83
- Subgraph Isomorphism Problem — 0.83
- Graph Sphericity — 0.83
- Pathwidth — 0.83
Computed from structural-signature embeddings · 2026-09-08