The smallest integer k such that the vertices of a graph can be colored with k colors and no two adjacent vertices share the same color (a proper vertex coloring).

Principle

The chromatic number measures how a graph can be partitioned into independent sets: it is the minimal number of color classes needed so that each class is an independent set.

Demonstration

A complete graph on n vertices has chromatic number n. Any bipartite graph with at least one edge has chromatic number 2. An odd cycle C_{2m+1} has chromatic number 3.

Misapplication

Confusing vertex chromatic number with edge chromatic number (chromatic index), fractional or list chromatic numbers, or assuming naive bounds (e.g., χ ≤ Δ+1) hold as equalities without checking exceptions covered by Brooks' theorem.

Consequence

Chromatic number constrains graph colorings in scheduling and register allocation problems, gives information about clique structure (clique number is a lower bound), and is computationally hard to determine (NP-hard decision for k≥3).

Reversal

The inverse notion is allowing improper colorings that permit adjacent equal colors, which reduces the needed color count; clique cover size or independence number provide alternative partition measures.

Boundary

Defined for finite and infinite graphs (where the chromatic number may be infinite); for directed graphs and hypergraphs the analogous notions differ and require adapted definitions (e.g., oriented chromatic number, hypergraph colorings).

Semantic Tension

Tension between chromatic number and clique number (lower bound), chromatic polynomial (counts colorings), and fractional or list chromatic numbers which refine or relax the definition and can diverge from χ.

Synthesis

The chromatic number is the minimal count of independent vertex classes needed to color a graph properly; it captures an essential combinatorial complexity and interacts with cliques, degrees, and coloring variants.