Coloring, colouring: различия между версиями

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

'''1.''' Let <math>G</math> be a graph and <math>S</math> be a set of colors. A '''coloring''' of <math>G</math> is

a mapping <math>f: V(G) \rightarrow S</math> from the vertex set <math>V(G)</math> into <math>S</math>

i.e., <math>f(x) \neq f(y)</math> whenever <math>x</math> and <math>y</math> are adjacent. This '''C.''' is called a '''proper''' ('''valid''',

<math>f</math> is called '''<math>k</math>-coloring''' of <math>G</math> if <math>f</math> is a coloring of <math>G</math> into <math>k</math> colors,

i.e. <math>k=|\{f(p): p\in V(G)\}|</math>.

It is <math>NP</math>-complete to decide if a given graph <math>G</math> admits

a <math>k</math>-coloring for a given <math>k</math> except for the cases <math>k</math> = 1 and <math>k</math> = 2.

Graph coloring remains <math>NP</math>-complete even on

planar graphs of degree at most 4.

'''2.'''  

*''Large-block schema''.