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 mathematics_logic_statistics 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.

In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face (or region) so that no two faces that share a boundary have the same color. Vertex coloring is often used to introduce graph coloring problems, since other coloring problems can be transformed into a vertex coloring instance.

For Chromatic number, the abstraction is narrower than the article's general subject matter: a positive case must preserve The smallest number of colors needed to color a graph is called its chromatic number, and is often denoted. Retaining only the name, a familiar example, or a downstream effect is insufficient. The specialist roles and tests remain anchored in mathematics_logic_statistics, which is why this identity is domain-specific rather than prime.

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.

Structural Signature¶

Sig role-phrases:

Defining carrier — Hence the result by Cole and Vishkin raised the question of whether there is a constant-time distributed algorithm for 3-coloring an n-cycle. showed that this is not possible: any deterministic distributed algorithm requires Ω( n) communication steps to reduce an n-coloring to a 3-coloring in an n-cycle.
Constitutive relation — 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.
Operating condition — In 1912, George David Birkhoff introduced the chromatic polynomial to study the coloring problem, which was generalised to the Tutte polynomial by W.
Recognition evidence — In 1960, Claude Berge formulated another conjecture about graph coloring, the strong perfect graph conjecture, originally motivated by an information-theoretic concept called the zero-error capacity of a graph introduced by Shannon.
Admissible variation — The conjecture remained unresolved for 40 years, until it was established as the celebrated strong perfect graph theorem by Chudnovsky, Robertson, Seymour, and Thomas in 2002.
Characteristic consequence — A complete graph K_n of n vertices requires \chi(K_n)=n colors.
Failure boundary — The same class of graphs is used for the construction of a family of triangle-free line segments in the plane, given by Pawlik et al.

What It Is Not¶

Not the whole field of mathematics_logic_statistics. The node requires the specific identity stated by The smallest number of colors needed to color a graph is called its chromatic number, and is often denoted.
Not an over-broad reading. Adjacent-vertex-distinguishing-total coloring : A total coloring with the additional restriction that any two adjacent vertices have different color sets.
Not an over-broad reading. However, in that paper he proved the five color theorem, saying that every planar map can be colored with no more than five colors, using ideas of Kempe.
Not an over-broad reading. Indeed, is the smallest positive integer that is not a zero of the chromatic polynomial.
Not automatically Graph Coloring. Retrieval proximity does not establish equivalence; the two identities must be compared by carrier, operation, and failure boundary.

Scope of Application¶

Chromatic number applies literally inside mathematics_logic_statistics wherever the source-defined carrier and relation can be established. Its documented habitats include:

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 vertices sharing the same edge have the same color.
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.
Chromatic polynomial. As the name indicates, for a given the function is indeed a polynomial in.

Outside mathematics_logic_statistics, the name should be retained only when these same operational conditions survive; otherwise the comparison belongs to the broader parent Pattern or should be marked as analogy.

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. The strongest recognition evidence in the frozen account is: In 1960, Claude Berge formulated another conjecture about graph coloring, the strong perfect graph conjecture, originally motivated by an information-theoretic concept called the zero-error capacity of a graph introduced by Shannon. A report should distinguish that evidence from a proxy, consequence, or common implementation. It should also state the qualification Adjacent-vertex-distinguishing-total coloring : A total coloring with the additional restriction that any two adjacent vertices have different color sets. so that a reader can reproduce the classification rather than infer it from topical resemblance.

Manages Complexity¶

Chromatic number compresses multiple mathematics_logic_statistics 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 K_n of n vertices requires \chi(K_n)=n colors. This compression makes cases comparable while leaving parameters, conventions, exceptions, and evidential quality explicit. It is lossy by design: local history and implementation details may be omitted only when they do not alter the defining relation.

Abstract Reasoning¶

Type the carrier. Identify the mathematics_logic_statistics 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. In 1960, Claude Berge formulated another conjecture about graph coloring, the strong perfect graph conjecture, originally motivated by an information-theoretic concept called the zero-error capacity of a graph introduced by Shannon.
Test variation. Change an implementation or setting while preserving the conjecture remained unresolved for 40 years, until it was established as the celebrated strong perfect graph theorem by Chudnovsky, Robertson, Seymour, and Thomas in 2002.
Run the collapse test. Remove the defining operation; if the label still seems equally apt, only a topic or correlate was retained.
Reduce cautiously. When the specialist conditions cannot be carried, route the residual comparison to Pattern.

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. An outside case receives the specialist name only when the same typed roles and rejection conditions can be filled literally; otherwise the comparison remains an analogy pending later graph densification.

Examples¶

Canonical¶

For chordal graphs, and for special cases of chordal graphs such as interval graphs and indifference graphs, the greedy coloring algorithm can be used to find optimal colorings in polynomial time, by choosing the vertex ordering to be the reverse of a perfect elimination ordering for the graph. This case is canonical because it supplies a concrete carrier and lets the defining relation be checked rather than merely named.

Mapped back: carrier → the entities in the documented case; operation → The smallest number of colors needed to color a graph is called its chromatic number, and is often denoted ; recognition evidence → In 1960, Claude Berge formulated another conjecture about graph coloring, the strong perfect graph conjecture, originally motivated by an information-theoretic concept called the zero-error capacity of a graph introduced by Shannon

Applied / In Practice¶

Kempe had already drawn attention to the general, non-planar case in 1879, and many results on generalisations of planar graph coloring to surfaces of higher order followed in the early 20^th century. The applied case shows how the identity is used under a second setting or qualification while keeping the same operative relation.

Mapped back: changed setting → History; invariant → The smallest number of colors needed to color a graph is called its chromatic number, and is often denoted ; boundary → the case exits the class when adjacent-vertex-distinguishing-total coloring : A total coloring with the additional restriction that any two adjacent vertices have different color sets

Structural Tensions¶

T1 — Stable identity versus admissible variation. Adjacent-vertex-distinguishing-total coloring : A total coloring with the additional restriction that any two adjacent vertices have different color sets. The tension matters because emphasizing only one side either dissolves the identity or overstates what the evidence and domain conventions warrant.

Diagnostic: Which changes preserve the defining relation, and which replace it?

T2 — Recognition versus proxy. However, in that paper he proved the five color theorem, saying that every planar map can be colored with no more than five colors, using ideas of Kempe. The tension matters because emphasizing only one side either dissolves the identity or overstates what the evidence and domain conventions warrant.

Diagnostic: Does the cited evidence establish the identity or only a correlated sign?

T3 — Definition versus implementation. Indeed, is the smallest positive integer that is not a zero of the chromatic polynomial. The tension matters because emphasizing only one side either dissolves the identity or overstates what the evidence and domain conventions warrant.

Diagnostic: Is the observed implementation constitutive, optional, or merely common?

T4 — Scope versus overextension. Hoffman's bound: Let W be a real symmetric matrix such that W_{i,j} = 0 whenever (i,j) is not an edge in G. The tension matters because emphasizing only one side either dissolves the identity or overstates what the evidence and domain conventions warrant.

Diagnostic: Can every claimed application fill the same typed roles without metaphor?

T5 — Transfer versus domain accent. Hence the result by Cole and Vishkin raised the question of whether there is a constant-time distributed algorithm for 3-coloring an n-cycle. showed that this is not possible: any deterministic distributed algorithm requires Ω( n) communication steps to reduce an n-coloring to a 3-coloring in an n-cycle. The tension matters because emphasizing only one side either dissolves the identity or overstates what the evidence and domain conventions warrant.

Diagnostic: Does the receiving case instantiate Chromatic number literally, co-instantiate Pattern, or only resemble it?

T6 — Autonomy versus reduction. 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. The tension matters because emphasizing only one side either dissolves the identity or overstates what the evidence and domain conventions warrant.

Diagnostic: What does Chromatic number distinguish that the broader parent Pattern leaves together?

Structural–Framed Character¶

Chromatic number is structural-leaning. Its structural side is the repeatable organization summarized by The smallest number of colors needed to color a graph is called its chromatic number, and is often denoted. Its framed side is the mathematics_logic_statistics vocabulary that fixes the carrier, evidence, exceptions, and admissible transformations.

Evaluative weight: the identity can be stated descriptively even when applications carry practical stakes. Human-practice dependence: the source-grounded carrier determines whether the relation exists independently or is constituted by a practice. Institutional origin: disciplinary conventions stabilize the name and test. Vocabulary portability: In 1912, George David Birkhoff introduced the chromatic polynomial to study the coloring problem, which was generalised to the Tutte polynomial by W. Import versus recognition: literal transfer requires the same mechanism; shape alone is analogy.

Its portable skeleton is Pattern. Its character: a recurring specialist identity whose thin organization can be abstracted, while its operational meaning remains domain-bound.

Structural Core vs. Domain Accent¶

What is skeletal. The smallest number of colors needed to color a graph is called its chromatic number, and is often denoted . The stable skeleton is the typed relation expressed in that definition and the entry's recognition and collapse tests. The source identifies these operative conditions: Hence the result by Cole and Vishkin raised the question of whether there is a constant-time distributed algorithm for 3-coloring an n-cycle. showed that this is not possible: any deterministic distributed algorithm requires Ω( n) communication steps to reduce an n-coloring to a 3-coloring in an n-cycle. 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. It further constrains recognition and variation through: In 1912, George David Birkhoff introduced the chromatic polynomial to study the coloring problem, which was generalised to the Tutte polynomial by W. In 1960, Claude Berge formulated another conjecture about graph coloring, the strong perfect graph conjecture, originally motivated by an information-theoretic concept called the zero-error capacity of a graph introduced by Shannon.

What is domain-bound. mathematics logic statistics supplies the operative entities, technical vocabulary, warrants, and exceptions that make Chromatic number literal. Its documented scope includes the condition that One of the major applications of graph coloring, register allocation in compilers, was introduced in 1981. Another bounded application condition is that 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. These are not decorative examples; they determine which carrier and evidence can fill the abstraction's roles.

Why no parent is asserted. Removing those specialist details does not currently yield one live catalog node that is a necessary genus for every instance. The entry is therefore approved as unparented rather than attached by topical resemblance. Its collapse evidence remains specific—The conjecture remained unresolved for 40 years, until it was established as the celebrated strong perfect graph theorem by Chudnovsky, Robertson, Seymour, and Thomas in 2002.—and future graph densification may discover a defensible relation only if it preserves that boundary.

This entry is a kind of Graph Invariant.

Approved unparented node. No current live node supplies a defensible necessary genus or structural prerequisite for Chromatic number. The reviewed identity is: The smallest number of colors needed to color a graph is called its chromatic number, and is often denoted. The accelerated suggestion was declined because topical or lexical similarity does not establish hierarchy; the node is admitted without a parent pending later graph densification.
Related reasoning operations. Evidence, representation, comparison, classification, transformation, or evaluation may participate in particular cases, but participation does not make any one of them a necessary parent of every instance.

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

Not to Be Confused With¶

Pattern. The parent omits the specialist differentia. Tell: Can the case establish The smallest number of colors needed to color a graph is called its chromatic number, and is often denoted ?
Graph Coloring. Conflict-free labeling so that no two items joined by a conflict edge share a label. Tell: Which entry's carrier, operation, and failure condition are satisfied?
Conflict-free coloring. A hypergraph vertex coloring in which every hyperedge contains at least one vertex whose color occurs exactly once within that edge. Tell: Which entry's carrier, operation, and failure condition are satisfied?
Greedy coloring. A sequential graph-coloring algorithm that assigns each vertex the first available color not used by already colored neighbors. Tell: Which entry's carrier, operation, and failure condition are satisfied?
A measurement, proxy, or consequence. Those may provide evidence without being the identity. Tell: Would Chromatic number remain present if the detector or downstream effect changed?
A metaphorical analogue. A similar shape outside mathematics_logic_statistics lacks the specialist mechanism. Tell: Do the native roles transfer literally, or only the parent Pattern?

References¶

Frozen Wikipedia discovery revision: https://en.wikipedia.org/wiki/Graph_coloring (revision 1369837144).
Preserved source candidate: https://mathworld.wolfram.com/ChromaticNumber.html
Preserved source candidate: https://mathworld.wolfram.com/EulerCharacteristic.html
Preserved source candidate: http://www.math-inst.hu/~p_erdos/1951-01.pdf
Preserved source candidate: https://web.archive.org/web/20160310003706/http://www.math-inst.hu/~p_erdos/1951-01.pdf
Preserved source candidate: http://www.hamilton.ie/ken_duffy/Downloads/cfl.pdf
Preserved source candidate: http://portal.acm.org/citation.cfm?id=803884
Preserved source candidate: https://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1613&context=cstech
Preserved source candidate: https://dx.doi.org/10.1016/0304-3975%2891%2990081-C

The frozen Wikipedia revision is discovery provenance. The retained source set was reviewed for identity, formal or operational relation, and scope. The encyclopedia's structural synthesis is bounded to those claims; a thin authority surface is recorded as a nonblocking source-strengthening repair rather than concealed.