## chromatic number- 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. - 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• TYPES OF NUMBER | |||||

Home • About • Copyright © The Worlds of David Darling • Encyclopedia of Alternative Energy • Contact |