Chromaticzahl

Chromaticzahl, denoted χ(G), is the smallest number of colors needed to color the vertices of a graph G so that adjacent vertices have different colors. Such a coloring is called a proper vertex coloring. The value of χ(G) depends on the structure of G, with χ(G) ≥ 1 for any nonempty graph and χ(G) = 1 precisely for edgeless graphs. For complete graphs K_n, χ(K_n) = n; for bipartite graphs χ(G) ≤ 2; a cycle C_n has χ(C_n) = 2 if n is even and χ(C_n) = 3 if n is odd.

Two standard families reserve intuition: planar graphs have χ ≤ 4 by the four color theorem; Brook's theorem gives χ(G) ≤ Δ(G) for connected graphs not equal to a complete graph or an odd cycle, where Δ is the maximum degree. The chromatic polynomial P_G(λ) counts the number of proper colorings with λ colors, and χ(G) is the smallest λ for which P_G(λ) > 0.

Computationally, determining χ(G) is NP-hard, and the decision problem "is χ(G) ≤ k?" is NP-complete. Exact computations are feasible only for small graphs or special classes; many algorithms focus on bounds, heuristics, or exhaustive search.

Variants include list coloring, where each vertex has its own palette of allowed colors; edge coloring, with the edge chromatic number χ′(G); and the more general concept of total coloring. Applications appear in scheduling, register allocation, and frequency assignment.

Historically, the concept originated with Francis Guthrie in 1852 and has since become central in graph theory. The term Chromaticzahl is mainly used in German-language literature, while χ(G) remains standard in English.