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.

Литература

• Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.