List coloring¶

List coloring denotes generalization of graph coloring in which each vertex has a list of allowed colors in graph coloring.

Version: v1 · 2026-09-28 · History
Domain-specific #: 10439
Domain group: Formal Sciences
Origin domain: Mathematics
Subdomains: Graph Coloring, Graph Theory → Mathematics

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.

Every k-choosable graph is k-colorable by giving all vertices the same k colors, but the converse can fail dramatically. Even bipartite graphs with chromatic number two may require larger lists because an adversarial pattern of local permissions can block every compatible choice. More generally, f-choosability permits a different guaranteed list size f(v) at each vertex. Structural theorems relate choosability to degree, degeneracy, planarity, kernels, and orientations, while algorithms seek a coloring for a particular list instance. Variants include edge list coloring, online list coloring, correspondence coloring, and applications where frequencies, time slots, labels, or resources differ by location.

List coloring is not ordinary coloring performed with named colors, and the list chromatic number is not the number of distinct colors ultimately used. A particular graph may be colorable from one small list assignment without being k-choosable, because choosability demands success for every assignment of that size. Lists are permissions, not preferences, and properness still enforces adjacency conflicts. The abstraction is locally restricted conflict avoidance: compatible labels must be selected from heterogeneous feasible sets under a shared graph of pairwise exclusions.

Structural Signature¶

Sig role-phrases:

the conflict graph — vertices representing objects and edges representing pairs that cannot share a label
the vertex-specific list L(v) — local set of colors or resources permitted at each vertex
the selection function — choice of exactly one allowed color for every vertex
the properness constraint — adjacent vertices required to receive distinct selected colors
the particular-instance problem — finding a coloring for one supplied family of lists
the universal choosability test — success demanded for every list assignment of at least a declared size
the choice number — minimum uniform list size guaranteeing that universal success
the ordinary-coloring relation — common palette recovered by assigning identical lists, making choosability the stronger property
the heterogeneous-availability effect — adversarial local permissions obstructing graphs that use few colors under a global palette
the extension family — f-choosability, edge lists, online lists, correspondence coloring, and resource-allocation interpretations varying the local constraint regime

What It Is Not¶

Not ordinary graph coloring with differently named global colors. Each vertex has its own permission set.
Not measured by the number of colors used in one successful coloring. The choice number is the list size guaranteeing success for every assignment.
Not established by one easy list instance. A graph is k-choosable only if every list assignment of size at least k can be colored.
Not equivalent to k-colorability. Giving all vertices one palette recovers ordinary coloring, but adversarial heterogeneous lists can require larger k.
Not a preference-ranking problem. Lists specify allowed choices, not desirability among them.
Not free of ordinary adjacency conflicts. Selected colors must still differ across every edge.
Not identical to edge, online, or correspondence coloring. Those variants move the lists or alter when and how local conflicts are specified.

Scope of Application¶

List coloring is a graph-theoretic instrument and applies when each vertex has its own permitted set of labels and adjacent vertices must receive different selected labels.

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.
Structural graph theory. Degree, degeneracy, planarity, kernels, and orientations yield sufficient conditions.
Algorithm design. One supplied list instance is solved under explicit complexity and output requirements.
Applicability boundary. List coloring is not ordinary coloring with renamed colors, a preference ranking, or a count of colors used in one solution, and success on one instance does not prove k-choosability; graph, lists, shared color identity, properness, k- or f-quantifier, and whether vertex, edge, online, or correspondence coloring is intended must be stated before results transfer.

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. The sharper graph question is how adversarial local availability interacts with adjacency and whether structural bounds, orientations, kernels, or polynomial methods guarantee a valid selection for all permitted list assignments.

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. This representation models scheduling and assignment constraints directly and reveals why a low chromatic number may not suffice. Structural bounds, orientations, kernels, and probabilistic arguments can then certify feasibility without enumerating every allowed-color combination.

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. List coloring does not mean coloring a list data structure, and an ordinary k-coloring does not prove k-choosability.

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.

Examples¶

Canonical¶

In a scheduling graph, adjacent jobs cannot share a time slot. Job v permits only L(v)={red,blue}, another only {blue,green}, and so on. A list coloring selects one permitted color per vertex while separating every adjacent pair. Ordinary three-coloring is the special case in which every list is the same three-color palette. A graph can be three-colorable yet fail for some adversarial three-element lists, so three-choosability is stronger: it requires success for every list assignment of size at least three.

Mapped back: Jobs/edges form the conflict graph, local palettes the vertex-specific list L(v), chosen slots the selection function, and conflicts the properness constraint. One assignment is the particular-instance problem; all size-k assignments the universal choosability test, defining the choice number.

Applied / In Practice¶

A frequency planner gives each transmitter a locally available channel list shaped by regulation and interference. An algorithm finds one valid assignment, then analysts ask whether the network is robustly k-choosable under any lists of that size. Set-based lists, online arrivals, edge demands, and correspondence constraints are modeled as distinct extensions. A shared global palette result is not used to promise success under heterogeneous local availability.

Mapped back: Availability demonstrates the heterogeneous-availability effect, common palette the ordinary-coloring relation, and alternate regimes the extension family.

Structural Tensions¶

T1 — Identity versus admissible variation. List coloring must remain recognizable across legitimate variants. Admissible variation is bounded by this condition: Transmitters have locally available channels while interference edges forbid shared choices. The stable element is expressed by this invariant: List coloring denotes generalization of graph coloring in which each vertex has a list of allowed colors in graph coloring. Treating every surface change as a new abstraction fragments the identity, while allowing a change to the constitutive relation produces a false positive.

Diagnostic: After the proposed variation, can an analyst still establish this invariant: List coloring denotes generalization of graph coloring in which each vertex has a list of allowed colors in graph coloring?

T2 — Recognition versus proxy. The domain needs observable or inferential evidence for List coloring, but the evidence is not automatically the identity. The working recognition rule is: the universal choosability test — success demanded for every list assignment of at least a declared size. A familiar indicator can occur without the defining relation, and the relation can persist when a customary detector is unavailable.

Diagnostic: Does the evidence establish the defining claim—List coloring denotes generalization of graph coloring in which each vertex has a list of allowed colors in graph coloring—or only a correlated sign?

T3 — Definition versus operational judgment. A compact definition aids reuse, whereas actual classification in graph coloring can require expert decisions about boundary conditions, measurements, conventions, or exceptions. Every k-choosable graph is k-colorable by giving all vertices the same k colors, but the converse can fail dramatically. The definition must constrain those judgments without pretending that every admissible case can be recognized from a label alone.

Diagnostic: Which observation would make a competent practitioner reject the classification under the stated definition?

T4 — Scope versus overextension. List coloring has a genuine habitat in which transmitters have locally available channels while interference edges forbid shared choices. Yet List coloring is not ordinary coloring with renamed colors, a preference ranking, or a count of colors used in one solution, and success on one instance does not prove k-choosability; graph, lists, shared color identity, properness, k- or f-quantifier, and whether vertex, edge, online, or correspondence coloring is intended must be stated before results transfer. A useful application map therefore has to be broad enough to cover recurring practice and narrow enough to exclude merely topical or metaphorical occurrences.

Diagnostic: Can the claimed application fill the same carrier and relation roles, or has only the name traveled?

T5 — Transfer versus domain accent. Knowledge about List coloring can travel within its home domain, and some structural lessons may travel farther. 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. What transfers must be separated from the specialist vocabulary, warrant, and closure conditions that remain anchored in graph coloring.

Diagnostic: Is the receiving case a literal instance of List coloring, a co-instance of Pattern, or only an analogy?

T6 — Autonomy versus reduction. List coloring is a strict specialization of Graph Coloring, but the edge does not erase the domain differentia. The broader node supplies only the necessary structural relation; graph coloring supplies the carrier, warrant, boundary, and exception conditions expressed by this identity: List coloring denotes generalization of graph coloring in which each vertex has a list of allowed colors in graph coloring. The entry is over-split if those conditions add no discriminating work and under-specified if the parent alone is used for cases that require them.

Diagnostic: Can a domain expert use the added conditions to distinguish List coloring from another case that equally instantiates Graph Coloring?

Structural–Framed Character¶

List coloring is mixed: structurally specifiable but materially dependent on its disciplinary frame. Its structural side consists of the carrier the conflict graph — vertices representing objects and edges representing pairs that cannot share a label and the constitutive relation List coloring denotes generalization of graph coloring in which each vertex has a list of allowed colors in graph coloring. Its framed side comes from graph coloring, which fixes what the terms denote, what counts as evidence, and when a qualification or exception defeats the classification.

Across the principal tests, the entry is not merely a free-floating pattern. Evaluative weight: the identity can be stated descriptively even when its use has practical or normative consequences. Practice dependence: the universal choosability test — success demanded for every list assignment of at least a declared size. Institutional stabilization: disciplinary conventions may stabilize the name and test without necessarily creating every underlying event or relation. Vocabulary portability: the invariant is List coloring denotes generalization of graph coloring in which each vertex has a list of allowed colors in graph coloring. Import versus recognition: an outside case qualifies literally only if the same typed roles and collapse condition are available; otherwise the comparison is analogical.

The reusable remainder is Graph Coloring under a reviewed subsumption relation. That node preserves the necessary cross-domain organization after the graph coloring-specific carrier, evidence, and exceptions are removed. List coloring remains autonomous because its recognition and collapse conditions distinguish cases that the parent alone leaves together.

Structural Core vs. Domain Accent¶

What is skeletal. The portable skeleton is a typed carrier organized by a constitutive relation, an invariant, a recognition test, and a collapse condition. Here the carrier is the conflict graph — vertices representing objects and edges representing pairs that cannot share a label. The decisive relation is List coloring denotes generalization of graph coloring in which each vertex has a list of allowed colors in graph coloring, which also states the controlling invariant at this level. Stripped of specialist nouns, this organization is represented by Pattern.

What is domain-bound. graph coloring supplies the actual objects or agents, admissible transformations, units or conventions, standards of warrant, and named exceptions. In this case, recognition requires evidence for the universal choosability test — success demanded for every list assignment of at least a declared size. Admissible variation is bounded by the condition that transmitters have locally available channels while interference edges forbid shared choices, and the classification collapses when each vertex has its own permission set. These are constitutive differentia, not illustrative decoration.

Why it remains a domain-specific node. The reviewed DAG relation is subsumption to Graph Coloring. Outside graph coloring, the parent captures only the reusable structural remainder. The specialist name remains literal only where the universal choosability test — success demanded for every list assignment of at least a declared size can be established under the domain's standards of warrant.

This entry is a kind of Graph Coloring.

Immediate parent — Graph Coloring (subsumption). 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. The parent supplies the necessary broader identity—Conflict-free labeling so that no two items joined by a conflict edge share a label.—while the candidate adds the source-domain carrier, recognition rule, and failure conditions. The defining source account begins: 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.
Nearest catalog surface declined — Graph Coloring. Its rematch score was 0.332383. Retrieval proximity did not establish synonymy or parentage; the carrier, invariant, and collapse condition remain different.
Related reasoning operations. Evidence, comparison, boundary testing, and representation can support a case without becoming additional DAG parents.

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

Not to Be Confused With¶

Graph Coloring. This is the reviewed immediate parent or structural prerequisite, not a synonym. Tell: retain List coloring only when the domain-specific relation List coloring denotes generalization of graph coloring in which each vertex has a list of allowed colors in graph coloring. and its source-domain warrant are established; otherwise route the case to Graph Coloring.
Greedy Coloring. This is the closest catalog retrieval surface, not an accepted synonym or parent. Tell: Ask which entry's carrier, invariant, and collapse test the case actually satisfies; shared vocabulary or a score of 0.761639 is insufficient.
Not ordinary graph coloring with differently named global colors. Each vertex has its own permission set. Tell: Require the positive recognition condition that the universal choosability test — success demanded for every list assignment of at least a declared size.
Not measured by the number of colors used in one successful coloring. The choice number is the list size guaranteeing success for every assignment. Tell: Replace the familiar surface feature and test whether list coloring denotes generalization of graph coloring in which each vertex has a list of allowed colors in graph coloring.
A detector, representation, or consequence. A method may reveal List coloring, a notation may describe it, and an outcome may follow from it without any of those being identical to the abstraction. Tell: Would the defining relation remain if the present detector, notation, or downstream effect changed?
A metaphorical transfer. A case outside the home domain may resemble the structure while lacking its native role types and standards of warrant. Tell: If only the general organization survives, route the comparison to Pattern rather than treating it as another List coloring instance.

References¶

Frozen Wikipedia revision: https://en.wikipedia.org/wiki/List_coloring (revision 1327743713).
DOI: https://doi.org/10.1016/0012-365X(95)00350-6
DOI: https://doi.org/10.1006/jctb.1994.1062
DOI: https://doi.org/10.1007/BF01204715
DOI: https://doi.org/10.1016/0012-365X(95)00104-5
DOI: https://doi.org/10.1016/j.disc.2008.04.061
DOI: https://doi.org/10.1109/VETECF.2005.1558001
DOI: https://doi.org/10.1109/SPDP.1996.570312
Supporting reference preserved in the packet: http://www.math-inst.hu/~p_erdos/1980-07.pdf
Supporting reference preserved in the packet: https://web.archive.org/web/20160309235325/http://www.math-inst.hu/~p_erdos/1980-07.pdf
Supporting reference preserved in the packet: http://www.math.uri.edu/~eaton/TalkUriOct03P1.pdf
Supporting reference preserved in the packet: https://web.archive.org/web/20170829220122/http://www.math.uri.edu/~eaton/TalkUriOct03P1.pdf
Supporting reference preserved in the packet: http://www.math.uri.edu/~eaton/TalkUriOct03P2.pdf
Supporting reference preserved in the packet: https://web.archive.org/web/20170830012324/http://www.math.uri.edu/~eaton/TalkUriOct03P2.pdf
Supporting reference preserved in the packet: http://www.ii.uib.no/~pinar/Choosability.pdf
Supporting reference preserved in the packet: http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/GraphTheoryIII.pdf

The frozen Wikipedia revision is discovery provenance. The cited source set was reviewed for identity, formal or operational relation, and scope. The encyclopedia's structural synthesis is bounded to those claims; URL transport failure alone was not treated as substantive contradiction.