info prev up next book cdrom email home

Chromatic Number

The fewest number of colors $\gamma(G)$ necessary to color a Graph or surface. The chromatic number of a surface of Genus $g$ is given by the Heawood Conjecture,

\gamma(g)=\left\lfloor{{\textstyle{1\over 2}}(7+\sqrt{48g+1}\,)}\right\rfloor ,

where $\left\lfloor{x}\right\rfloor $ is the Floor Function. $\gamma(g)$ is sometimes also denoted $\chi(g)$. 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, ... (Sloane's A000934).

The fewest number of colors necessary to color each Edge of a Graph so that no two Edges incident on the same Vertex have the same color is called the ``Edge chromatic number.''

See also Brelaz's Heuristic Algorithm, Chromatic Polynomial, Edge-Coloring, Euler Characteristic, Heawood Conjecture, Map Coloring, Torus Coloring


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

Sloane, N. J. A. Sequence A000934/M3292 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.

© 1996-9 Eric W. Weisstein