TOPICS
Search

Chromatic Number

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
ChromaticNumber

The chromatic number of a finite simple graph G with at least one graph vertex is the smallest number of colors needed to color the vertices of G so that no two adjacent vertices share the same color (Harary and Palmer 1973, p. 269; Skiena 1990, p. 210), i.e., the smallest value of k possible to obtain a k-coloring. Minimum vertex colorings and chromatic numbers for a sample of graphs are illustrated above. The graph with no vertices has chromatic number 0 by convention.

The chromatic number of a graph G is most commonly denoted chi(G) (e.g., Skiena 1990, West 2000, Godsil and Royle 2001, Pemmaraju and Skiena 2003), but occasionally also gamma(G).

Empty graphs with at least one graph vertex have chromatic number 1 (OEIS A000012), while bipartite graphs with at least one graph edge have chromatic number 2.

The chromatic number of a graph G is also the smallest nonnegative integer z for which the chromatic polynomial pi_G(z)>0. The optimization problem of finding a minimum vertex coloring, and hence calculating the chromatic number, is the vertex coloring problem.

Computation of the chromatic number of a graph is implemented in the Wolfram Language as VertexChromaticNumber[g]. Precomputed chromatic numbers for many named graphs can be obtained using GraphData[graph, "ChromaticNumber"].

The chromatic number of a graph must be greater than or equal to its clique number. A graph is called a perfect graph if, for each of its induced subgraphs g_i, the chromatic number of g_i equals the largest number of pairwise adjacent vertices in g_i. A graph for which the clique number is equal to the chromatic number (with no further restrictions on induced subgraphs) is said to be weakly perfect.

For a simple graph with at least one graph edge and largest and least adjacency eigenvalues theta_(max) and theta_(min), the Hoffman ratio bound gives

chi(G)>=[1-(theta_(max))/(theta_(min))],

where [x] denotes the ceiling function (Brouwer and Haemers 2012). For a regular graph of vertex degree k, the largest graph eigenvalue is k. In this case the result also follows from chi(G)>=[v/alpha(G)] and the Hoffman ratio bound, where v is the number of vertices and alpha(G) is the independence number.

By definition, the edge chromatic number of a graph G equals the chromatic number of the line graph L(G).

Brooks' theorem states that the chromatic number of a connected simple graph with at least one graph vertex is at most the maximum vertex degree Delta, unless the graph is complete or an odd cycle, in which case Delta+1 colors are required (Brooks 1941).

A graph with chromatic number <=2 is said to be bicolorable, and a graph with chromatic number <=3 is said to be three-colorable. In general, a graph with chromatic number k is said to be a k-chromatic graph, and a graph with chromatic number <=k is said to be k-colorable.

The following table gives the chromatic numbers for some named classes of graphs.

graph Ggamma(G)
complete graph K_nn
cycle graph C_n, n>=3{3 for n odd; 2 for n even
star graph S_n, n>12
wheel graph W_n, n>=4{3 for n odd; 4 for n even

For any two positive integers g and k, there exists a graph of girth at least g and chromatic number at least k (Erdős 1959, 1961; Lovász 1968; Skiena 1990, p. 215; Bollobás and West 2000).

The chromatic number of a closed surface that is connected and orientable is the largest chromatic number of a graph embeddable in it. For genus g>=0, its value is

gamma(g)=|_1/2(7+sqrt(48g+1))_|,

where |_x_| is the floor function. For g>=1, this is the Heawood conjecture, proved by Ringel and Youngs (1968). For g=0, sufficiency of four colors is the four-color theorem. gamma(g) is sometimes also denoted chi(g) (which is unfortunate, since chi(g)=2-2g commonly refers to the Euler characteristic). For g=0, 1, ..., the first few values of chi(g) are 4, 7, 8, 9, 10, 11, 12, 12, 13, 13, 14, 15, 15, 16, ... (OEIS A000934).

A different invariant, the achromatic number, maximizes the number of colors in a proper vertex coloring for which every pair of colors appears at the ends of a graph edge. It is at least the chromatic number. Timmons (2026) determined it for sufficiently large Peisert graphs.

See also

Betti Number, Bicolorable Graph, Brelaz's Heuristic Algorithm, Brooks' Theorem, Choice Number, Chromatic Invariant, Chromatic Polynomial, Correspondence Chromatic Number, Cyclic Chromatic Number, Dichromatic Number, Edge Chromatic Number, Edge Coloring, Euler Characteristic, Fractional Chromatic Number, Genus, Heawood Conjecture, Hoffman Ratio Bound, k-Chromatic Graph, k-Colorable Graph, Local Antimagic Chromatic Number, Map Coloring, Perfect Graph, Quantum Chromatic Number, Three-Colorable Graph, Torus Coloring, Vector Chromatic Number, Vertex Coloring Problem Explore this topic in the MathWorld classroom

Explore with Wolfram|Alpha

References

Bollobás, B. and West, D. B. "A Note on Generalized Chromatic Number and Generalized Girth." Disc. Math. 213, 29-34, 2000. https://doi.org/10.1016/S0012-365X(99)00165-X.Brooks, R. L. "On Colouring the Nodes of a Network." Proc. Cambridge Philos. Soc. 37, 194-197, 1941. https://doi.org/10.1017/S030500410002168X.Brouwer, A. E. and Haemers, W. H. Spectra of Graphs. New York: Springer, 2012. https://doi.org/10.1007/978-1-4614-1939-6.Chartrand, G. "A Scheduling Problem: An Introduction to Chromatic Numbers." §9.2 in Introductory Graph Theory. New York: Dover, pp. 202-209, 1985.Eppstein, D. "The Chromatic Number of the Plane." https://ics.uci.edu/~eppstein/junkyard/plane-color.html.Erdős, P. "Graph Theory and Probability." Canad. J. Math. 11, 34-38, 1959. https://doi.org/10.4153/CJM-1959-003-9.Erdős, P. "Graph Theory and Probability II." Canad. J. Math. 13, 346-352, 1961.Gardner, M. The Sixth Book of Mathematical Games from Scientific American. Chicago, IL: University of Chicago Press, p. 9, 1984.Godsil, C. and Royle, G. Algebraic Graph Theory. New York: Springer-Verlag, 2001.Harary, F. and Palmer, E. M. "A Survey of Graphical Enumeration Problems." In A Survey of Combinatorial Theory (Ed. J. N. Srivastava). Amsterdam, Netherlands: North-Holland, pp. 259-275, 1973.Lovász, L. "On Chromatic Number of Finite Set-Systems." Acta Math. Acad. Sci. Hungar. 19, 59-67, 1968.Pemmaraju, S. and Skiena, S. Computational Discrete Mathematics: Combinatorics and Graph Theory in Mathematica. Cambridge, England: Cambridge University Press, 2003.Ringel, G. and Youngs, J. W. T. "Solution of the Heawood Map-Coloring Problem." Proc. Nat. Acad. Sci. USA 60, 438-445, 1968. https://doi.org/10.1073/pnas.60.2.438.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990.Sloane, N. J. A. Sequences A000012/M0003 and A000934/M3292 in "The On-Line Encyclopedia of Integer Sequences."Timmons, C. "The Achromatic Number of Paley Graphs, Peisert Graphs, and Related Cayley Graphs." 20 Oct 2026. https://arxiv.org/abs/2610.27510.West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 2000.

Referenced on Wolfram|Alpha

Chromatic Number

Cite this as:

Weisstein, Eric W. "Chromatic Number." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/ChromaticNumber.html

Subject classifications