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

References

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.'' http://www.ics.uci.edu/~eppstein/junkyard/plane-color/.

Sloane, N. J. A. Sequence A000934/M3292 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.