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: v1 · 2026-08-30 · History
Domain-specific #: 1967
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.^[1] Zaker develops the same definition, complexity, bounds, and well-colored-graph consequences.^[2]

The key contrast is with the chromatic number \(\chi(G)\), which minimizes colors over all proper colorings. Grundy number maximizes the count produced by a specified online rule over all orders. Thus \(\chi(G)\leq\Gamma(G)\leq\Delta(G)+1\), and the gap can be large.

Structural Signature¶

Recognition roles:

Finite simple graph: vertices are the items and edges are simultaneous-color conflicts.
Vertex ordering: an adversarial or existential sequence determines what first-fit sees.
First-fit rule: each arriving vertex receives the least positive unused neighbor color.
Properness invariant: adjacent vertices never share a color.
Lower-color witness condition: a vertex receiving color \(j\) has earlier neighbors in every color below \(j\).
Order extremization: color count is maximized over all orderings, not sampled from one run.
Graph invariant: the maximum depends only on the graph up to isomorphism.
Order-sensitivity interpretation: comparison with \(\chi(G)\) exposes worst-case greedy inefficiency.

Recognition test: exhibit an ordering whose first-fit run uses \(k\) colors, or equivalently a proper coloring with the lower-color witness property, and prove no ordering can use more. A single arbitrary greedy run provides only a lower bound on \(\Gamma(G)\).

What It Is Not¶

It is not the chromatic number, which is the minimum number in any proper coloring. It is not the greedy coloring number for one specified ordering, nor the minimum greedy count over orderings.

It is not the achromatic number or b-chromatic number. Those maximize colors under different completeness or color-dominating conditions. It is not online chromatic number, where an algorithm competes against adversarial arrival without choosing one fixed first-fit rule.

It is also unrelated to the Sprague–Grundy value of an impartial game position. The shared eponym does not create a mathematical identity: graph Grundy number concerns first-fit vertex 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)\).^[2] Later complexity work distinguishes Grundy Coloring from weak and connected variants and maps fixed-parameter behavior across graph classes.^[3]

The concept applies whenever a graph is colored by sequential first-fit and ordering effects matter. It does not automatically describe register allocation or scheduling systems with additional constraints unless their conflict model and algorithm reduce exactly to this graph process.

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\).

Two quantifiers must remain explicit:

\[ \Gamma(G)=\max_{\sigma\in S_{V(G)}}\operatorname{FF}(G,\sigma). \]

The maximum is over vertex permutations \(\sigma\); \(\operatorname{FF}\) is the color count from the fixed first-fit algorithm. Changing “max” to “min,” or optimizing over arbitrary coloring algorithms, defines another object.

The bound \(\Gamma(G)\leq\Delta(G)+1\) follows because a vertex assigned color \(j\) needs at least \(j-1\) differently colored neighbors. This bound can be loose but is a useful formula check.

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. A large gap warns that implementation details such as arrival order or preprocessing can dominate performance even though every output remains proper.

The number deliberately discards the distribution of color counts across orderings. Two graphs with equal \(\Gamma\) may have very different typical behavior. Average-case ordering analysis therefore requires more than the invariant.

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)\). For arbitrary non-induced subgraphs, removed edges can change first-fit witnesses, so one should not infer the same claim without proof.

A certificate for \(\Gamma(G)\geq k\) is a Grundy \(k\)-coloring. Verification checks properness and, for each color-\(j\) vertex, a neighbor in every lower color. This local certificate contrasts with the global maximization problem.

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.

The eponym must not transfer to game theory merely because both use a minimum-excluded operation. Graph Grundy coloring and Sprague–Grundy theory have distinct objects, operations, and outputs.

Examples¶

Four-vertex path¶

Let \(P_4\) have vertices \(v_1-v_2-v_3-v_4\). Process \(v_1,v_4,v_2,v_3\). The endpoints receive color 1; \(v_2\) sees color 1 and receives 2; \(v_3\) sees colors 1 and 2 and receives 3. Thus \(\Gamma(P_4)\geq3\). Its maximum degree is 2, so the degree bound gives \(\Gamma(P_4)\leq3\). Therefore \(\Gamma(P_4)=3\), while \(\chi(P_4)=2\).

Complete graph¶

For \(K_n\), every new vertex is adjacent to all earlier ones. First-fit uses a new color at every step for every ordering, so \(\Gamma(K_n)=\chi(K_n)=n\). This is high color count without order sensitivity.

Complete bipartite graph¶

For connected \(K_{m,n}\), first-fit cannot create a third color: a vertex on one side cannot simultaneously acquire lower-color witnesses arranged to force color 3 without violating the bipartition's shared adjacency structure. A two-color run exists, so \(\Gamma=2\). This contrasts with other bipartite graphs, including crown constructions, whose Grundy number can greatly exceed 2.^[4]

Structural Tensions¶

T1: Optimal coloring versus greedy vulnerability. \(\chi\) measures best possible use; \(\Gamma\) measures worst first-fit order. Diagnostic: Is the question minimizing over colorings or maximizing over first-fit orderings?

T2: Worst case versus typical order. One rare ordering can determine \(\Gamma\). Diagnostic: Does the application face adversarial order, or does it need a distributional performance measure?

T3: Local witnesses versus global computation. A proposed Grundy coloring is locally checkable, but finding the maximum is hard. Diagnostic: Is the task certificate verification or invariant optimization?

T4: Graph structure versus presentation control. Reordering can improve a deployed greedy heuristic even though \(\Gamma(G)\) is fixed. Diagnostic: Can the system choose an ordering, and if so should it optimize the actual run instead of only bounding the worst one?

T5: Autonomous invariant versus Graph Coloring reduction. Graph Coloring supplies proper assignments, but not maximum first-fit order sensitivity. Diagnostic: Does the analysis require the max-over-orders quantifier and lower-color witness property?

Structural–Framed Character¶

Grundy number is mathematically structural. It depends on graph adjacency, a fixed deterministic rule, and extremization over orderings; application values do not enter.

Its framing lies in selecting first-fit and worst-case order as the object of interest. That selection is conventional within graph algorithms, but once fixed the invariant is exact. The specialist graph vocabulary and witness structure support domain-specific classification.

Structural Core vs. Domain Accent¶

The portable core is hold a greedy rule fixed, vary input order adversarially, and retain the worst output statistic. Greedy Algorithm captures that broad reasoning.

The domain accent is proper vertex coloring, neighbor conflicts, smallest available colors, and lower-color witnesses. Those obligations do not travel across unrelated substrates.

Graph Coloring plus Greedy Algorithm does not compositionally close the node: their conjunction does not specify maximization over all orders, the resulting invariant, its witness characterization, or its specialized complexity questions.

Grundy Number presupposes prime:graph_coloring because every first-fit outcome is a proper vertex coloring and the invariant compares against chromatic structure. The proposed relation is composition, not specialization: a numerical graph invariant is not itself the generic coloring operation.

prime:greedy_algorithm explains the fixed local rule. It is declined as a second parent because Graph Coloring plus the dossier's first-fit definition already makes the operative domain relation explicit, and an extra edge would not improve placement.

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 (76^th 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

Computed from structural-signature embeddings · 2026-09-08

Not to Be Confused With¶

Chromatic number: minimum proper-color count, not maximum first-fit count.
Greedy run count: result for one ordering, only a lower bound on \(\Gamma\).
Achromatic number: maximum colors in a complete proper coloring under a different condition.
b-chromatic number: maximum colors with a dominating vertex in each color class.
Online chromatic number: performance under an online adversary with algorithm choice, not fixed first-fit extremization.
Graph Coloring Game: alternating strategic play rather than static ordering of first-fit.
Sprague–Grundy number: impartial-game value, unrelated despite the name.

References¶

[1] Claude A. Christen and Stanley M. Selkow, “Some Perfect Coloring Properties of Graphs,” Journal of Combinatorial Theory, Series B 27(1), 1979, 49–59, https://doi.org/10.1016/0095-8956(79)90067-4. registry ↩

[2] Manouchehr Zaker, “Results on the Grundy Chromatic Number of Graphs,” Discrete Mathematics 306(23), 2006, 3166–3173, https://doi.org/10.1016/j.disc.2005.06.044. registry ↩a ↩b

[3] Édouard Bonnet et al., “Complexity of Grundy Coloring and Its Variants,” Discrete Applied Mathematics 243, 2018, 99–114, https://doi.org/10.1016/j.dam.2017.12.022. registry ↩

[4] Tommy R. Jensen and Bjarne Toft, Graph Coloring Problems, Wiley, 1995, chapter 10, https://doi.org/10.1002/9781118032497.ch10. registry ↩