Coloring, colouring

Материал из WikiGrapp
Перейти к:навигация, поиск

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

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

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

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




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