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.

Version: v2 · 2026-09-19 · History
Domain-specific #: 1967
Domain group: Formal Sciences
Origin domain: Mathematics
Aliases: Grundy chromatic number

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.

How would you explain it like I'm…

Most Crayons Possible

Imagine dots joined by strings, and joined dots can't be the same color. You color one dot at a time, always picking the first color in your crayon line that its colored neighbors aren't using. If you pick the dots in a sneaky order, you can end up needing lots of crayons. The Grundy number is the most crayons this rule could ever make you use.

Worst-Order Coloring Number

In a graph, dots are connected by lines, and connected dots must get different colors. A simple rule called first-fit colors the dots one by one. Each dot gets color 1 if it can, otherwise color 2, and so on, avoiding colors its already-colored neighbors have. The number of colors you end up with depends on the order you visit the dots. The Grundy number is the largest number of colors any order can force. That can be much more than the fewest colors the graph really needs.

Maximum First-Fit Colors

The Grundy number of a graph is the maximum number of colors the first-fit greedy algorithm can use, taken over every possible order of the vertices. First-fit gives each vertex the smallest color number not used by its already-colored neighbors. Equivalently, it is the largest k for which there is a proper coloring where every vertex of color j touches a vertex of each smaller color. Compare the chromatic number, which is the minimum colors any proper coloring needs. The Grundy number instead measures how badly a sensible-looking step-by-step rule can do with a bad order. It always lies between the chromatic number and the maximum degree plus one.

The Grundy number Γ(G), also called the Grundy chromatic number, is the maximum number of colors that first-fit greedy coloring can produce on G over all vertex orderings. First-fit processes vertices in sequence and assigns each the least positive integer not already used on its colored neighbors. An equivalent static definition uses Grundy k-colorings. A Grundy k-coloring is a proper coloring in which every vertex colored j has neighbors of every color i < j, and Γ(G) is the largest k admitting one. Christen and Selkow introduced the invariant, and Zaker studied its complexity, bounds, and links to well-colored graphs. It contrasts with the chromatic number χ(G): χ minimizes over all proper colorings, while Γ maximizes the output of one fixed online rule over all orders. Hence χ(G) ≤ Γ(G) ≤ Δ(G)+1, and the gap can be large. It quantifies the worst-case ordering sensitivity of greedy coloring.

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

\[ \chi(G)\leq\Gamma(G)\leq\Delta(G)+1. \]

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) — outgoing typed relations

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 → presupposes Graph Coloring → is a kind of Partition → presupposes Set and Membership

Neighborhood in Abstraction Space¶

Grundy Number sits in a sparse region of the domain-specific corpus (70^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (2769 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-25