K-Colored graph: различия между версиями

'''<math>k</math>-Colored graph''' —  ''[[k-Раскрашенный граф|<math>\,k</math>-раскрашенный граф]].''

Let <math>\,k</math> be an integer. A '''<math>k</math>-colored graph''' is a [[graph, undirected graph, nonoriented graph|graph]] <math>\,G = (V,E)</math> together with a [[vertex]] ''[[coloring, colouring|coloring]]'' which is a mapping <math>\,f: \; V\rightarrow S</math> such that

(1) each vertex is colored with one of the colors such that no two [[adjacent vertices]] have the same color (i.e., <math>\,f(x) \neq f(y)</math> whenever <math>\,x</math> and <math>\,y</math> are adjacent),

(2) <math>\,|S| = k</math> and each color is used at least once (i.e., <math>\,f</math> is surjective).

 

 

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