List coloring¶
List coloring denotes generalization of graph coloring in which each vertex has a list of allowed colors in graph coloring.
Core Idea¶
List coloring is a constrained form of proper graph coloring in which each vertex v has its own allowed set L(v), and a coloring must choose a color from L(v) while assigning different colors to adjacent vertices. The lists model local availability rather than a single global palette. A graph is k-choosable if every assignment of lists of size at least k admits a proper list coloring. Its list chromatic number, or choice number, is the least such k. This universal quantifier over list assignments makes choosability stronger than ordinary k-colorability.
Scope of Application¶
-
Frequency assignment. Transmitters have locally available channels while interference edges forbid shared choices.
-
Scheduling. Jobs or participants receive individual time-slot lists under pairwise conflict constraints.
-
Resource allocation. Heterogeneous feasibility sets replace a single global palette.
-
Precoloring extensions. Fixed or restricted vertices are incorporated through singleton or reduced lists.
-
Choosability theory. Success is required for every list assignment of a declared minimum size.
Clarity¶
List coloring requires each vertex to receive a proper color from its own allowed list. The universal definition of \(k\)-choosability—success for every assignment of lists of size at least \(k\)—is stronger than ordinary \(k\)-colorability, which uses one shared palette. This prevents a favorable list instance from proving a graph \(k\)-choosable.
Manages Complexity¶
List coloring compresses local color availability to a graph plus one allowed set per vertex. The analyst tracks list sizes, adjacency, choice number, and adversarial list structure rather than assuming one global palette. Ordinary coloring appears as the special branch where every list is identical; choosability quantifies success for all lists of a given size.
Abstract Reasoning¶
Constraint move. Assign each vertex a color from its own allowed list while requiring adjacent vertices to differ. Feasibility move. Search, reduce, or prove impossibility using graph structure and list sizes rather than assuming one common palette. Adversarial move. To establish k-choosability, show every assignment of lists of size k admits a coloring; to refute it, construct one failing assignment. Comparison move. Relate list chromatic number to ordinary chromatic number while studying their possible gap. Boundary move.
Knowledge Transfer¶
Within the home domain. List coloring transfers across graph theory, scheduling, frequency assignment, register allocation, and constrained resource assignment when each vertex has its own permitted color set and adjacent vertices must differ. List assignment, proper coloring, choosability, obstruction, and algorithm retain exact roles. Beyond the home domain (C — formal constraint model). It applies literally to any problem encoded as such a graph. Its boundary is representational: an ordinary k-coloring does not prove k-choosability, real scheduling constraints may require hyperedges or capacities, and calling options “colors” adds no guarantee that the encoding preserves every operational rule.
Relationships to Other Abstractions¶
Current abstraction List coloring Domain-specific
Parents (1) — more general patterns this builds on
-
List coloring is a kind of Graph Coloring Prime
List coloring is a domain-specific kind of Graph Coloring: List coloring denotes generalization of graph coloring in which each vertex has a list of allowed colors in graph coloring.
Hierarchy path (1) — routes to 1 parentless root
- List coloring → Graph Coloring → Partition → Set and Membership
Neighborhood in Abstraction Space¶
List coloring sits in a moderately populated region (58th percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.
Family — Graph Structures & Combinatorial Objects (44 abstractions)
Nearest neighbors
- Fractional Coloring — 0.90
- Edge Coloring — 0.86
- Graph canonization — 0.85
- Grundy Number — 0.85
- Graph Sphericity — 0.84
Computed from structural-signature embeddings · 2026-10-08