TYPES OF NUMBERS

• HOME • ABOUT • CATEGORIES • COPYRIGHT • NEWSLETTER

chromatic number

1. 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 NP-hard problem.


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

Related category