Coloring, colouring — раскраска.
1. Let be a graph and be a set of colors. A coloring of is a mapping from the vertex set into such that no two adjacent vertices have the same color, i.e., whenever and are adjacent. This C. is called a proper (valid, legitimate, good) coloring.
is called -coloring of if is a coloring of into colors, i.e. .
It is -complete to decide if a given graph admits a -coloring for a given except for the cases = 1 and = 2. Graph coloring remains -complete even on planar graphs of degree at most 4.
- Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.