Chromatic number¶

The smallest number of colors needed to color a graph is called its chromatic number, and is often denoted .

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

Core Idea¶

Chromatic number is treated here as the recurring mathematicslogicstatistics identity summarized by this source-grounded definition: The smallest number of colors needed to color a graph is called its chromatic number, and is often denoted. In graph theory, graph coloring is a methodic assignment of labels traditionally called "colors" to elements of a graph. The assignment is subject to certain constraints, such as that no two adjacent elements have the same color. Graph coloring is a special case of graph labeling.

How would you explain it like I'm…

The Fewest Crayons Number

Draw some dots and connect some of them with lines. Now color the dots so that two dots joined by a line never have the same color. The chromatic number is the smallest number of crayons you need to do that.

Fewest Colors Needed

A graph is a set of dots with lines connecting some pairs of them. Coloring a graph means giving each dot a color so that no two connected dots share a color. You could always use a different color for every dot, but that's wasteful. The chromatic number is the smallest number of colors that still works for that graph.

Minimum Proper Coloring Count

In graph theory, a vertex coloring assigns a color to every vertex so that any two vertices joined by an edge get different colors. The chromatic number is the smallest number of colors for which such a coloring exists. It is a single number describing the whole graph, not a particular coloring: showing one coloring with k colors proves the chromatic number is at most k, but proving it is exactly k also means showing that fewer colors cannot work. Related puzzles color edges or the faces of a map instead, but those can usually be converted into vertex coloring problems.

A proper vertex coloring of a graph G is an assignment of labels (colors) to vertices such that adjacent vertices receive different labels. The chromatic number of G, often written chi(G), is the minimum number of colors for which a proper vertex coloring exists. It is an invariant of the graph: it depends only on G, not on any particular coloring. Establishing chi(G) = k requires two parts: an upper bound, by exhibiting a proper k-coloring, and a lower bound, by showing no proper (k-1)-coloring exists. Graph coloring more generally is a special case of graph labeling, and edge colorings and face colorings of planar graphs are related problems that can be recast as vertex colorings. The concept is narrower than graph coloring as a topic: it is specifically the minimum.

Scope of Application¶

History. One of the major applications of graph coloring, register allocation in compilers, was introduced in 1981.
Definition and terminologyVertex coloring. When used without any qualification, a coloring of a graph almost always refers to a proper vertex coloring, namely a labeling of the graph's vertices with colors such that no two.
Definition and terminologyVertex coloring. Labels like red and blue are only used when the number of colors is small, and normally it is understood that the labels are drawn from the integers.
Definition and terminologyVertex coloring. Sometimes is used, since is also used to denote the Euler characteristic of a graph.
Chromatic polynomial. The chromatic polynomial is a function that counts the number of -colorings of.

Clarity¶

A clear use of Chromatic number names the carrier, the operative relation, and the conditions under which the source treats the identity as present. The minimal definition is The smallest number of colors needed to color a graph is called its chromatic number, and is often denoted.

Manages Complexity¶

Chromatic number compresses multiple mathematicslogicstatistics details into a stable diagnostic relation. The source shows both the central mechanism—in the following century, a vast amount of work was done and theories were developed to reduce the number of colors to four, until the four color theorem was finally proved in 1976 by Kenneth Appel and Wolfgang Haken.—and the practical consequence—a complete graph Kn of n vertices requires.

Abstract Reasoning¶

Type the carrier. Identify the mathematicslogicstatistics entities to which the claim applies.
State the relation. Use the source-grounded identity: The smallest number of colors needed to color a graph is called its chromatic number, and is often denoted.
Check operation and conditions. In 1912, George David Birkhoff introduced the chromatic polynomial to study the coloring problem, which was generalised to the Tutte polynomial by W.
Demand recognition evidence.

Knowledge Transfer¶

Within the home domain. Knowledge about Chromatic number transfers literally when a new case preserves the same carrier type, relation, and recognition test. One of the major applications of graph coloring, register allocation in compilers, was introduced in 1981. When used without any qualification, a coloring of a graph almost always refers to a proper vertex coloring, namely a labeling of the graph's vertices with colors such that no two vertices sharing the same edge have the same color. Beyond the home domain. No canonical parent is asserted for Chromatic number.

Relationships to Other Abstractions¶

Current abstraction Chromatic number Domain-specific

Parents (1) — more general patterns this builds on

Chromatic number is a kind of Graph Invariant Domain-specific

Chromatic number satisfies the defining boundary of Graph Invariant: A graph invariant is a value, polynomial, sequence, multiset, or other mathematical object assigned to a graph such that isomorphic graphs receive the same result, with its definition, graph category, and distinguishing power explicitly stated.

Hierarchy path (1) — routes to 1 parentless root

Chromatic number → Graph Invariant

Neighborhood in Abstraction Space¶

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

Family — Unclustered & Miscellaneous (2551 abstractions)

Nearest neighbors

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