- In graph theory, the minimum
number of colors needed to color (the vertices of) a connected
graph so that no two adjacent vertices are colored the same. In
the case of simple graphs, this so-called coloring problem can
be solved by inspection. In general, however, finding the chromatic
number of a large graph (and, similarly, an optimal coloring) is an
- In topology, the maximum number of
regions that can be drawn on a surface in such a way that each region
has a border in common with every other region. If each region is given
a different color, each color will border on every other color. The
chromatic number of a square, tube, or sphere, for example, is 4; in
other words, it is impossible to place more than four differently-colored
regions on one of these figures so that any pair has a common boundary.
"Chromatic number" also indicates the least number of colors needed
to color any finite map on a given surface. Again, this is 4 in the
case of the plane, tube, and sphere, as was proved quite recently in
the solution to the four-color
problem. The chromatic number, in both senses just described, is
7 for the torus, 6 for the Möbius
band, and 2 for the Klein bottle.
See also Betti number.