 |
|
| A B C D E F G H I J K L M N O P Q R S T U V W X Y Z |
|
|
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
Also on this site:
Encyclopedia of Alternative Energy & Sustainable Living
Encyclopedia of History
Transport Concepts & Designs (partner site)