Coloring, colouring

Coloring, colouring --- раскраска.

1. Let [math]\displaystyle{ G }[/math] be a graph and [math]\displaystyle{ S }[/math] be a set of colors. A coloring of [math]\displaystyle{ G }[/math] is a mapping [math]\displaystyle{ f: V(G) \rightarrow S }[/math] from the vertex set [math]\displaystyle{ V(G) }[/math] into [math]\displaystyle{ S }[/math] such that no two adjacent vertices have the same color, i.e., [math]\displaystyle{ f(x) \neq f(y) }[/math] whenever [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math] are adjacent. This C. is called a proper (valid, legitimate, good) coloring.

[math]\displaystyle{ f }[/math] is called [math]\displaystyle{ k }[/math]-coloring of [math]\displaystyle{ G }[/math] if [math]\displaystyle{ f }[/math] is a coloring of [math]\displaystyle{ G }[/math] into [math]\displaystyle{ k }[/math] colors, i.e. [math]\displaystyle{ k=|\{f(p): p\in V(G)\}| }[/math].

It is [math]\displaystyle{ NP }[/math]-complete to decide if a given graph [math]\displaystyle{ G }[/math] admits a [math]\displaystyle{ k }[/math]-coloring for a given [math]\displaystyle{ k }[/math] except for the cases [math]\displaystyle{ k }[/math] = 1 and [math]\displaystyle{ k }[/math] = 2. Graph coloring remains [math]\displaystyle{ NP }[/math]-complete even on planar graphs of degree at most 4.

2.

See

• Large-block schema.