List coloring

List coloring --- предписанная раскраска.

Let [math]\displaystyle{ V = \{v_{1}, \ldots, v_{n}\} }[/math] be the vertices of [math]\displaystyle{ G }[/math], [math]\displaystyle{ L_{i} }[/math] denote the list (= a set of admissible colors) associated with [math]\displaystyle{ v_{i} }[/math], and [math]\displaystyle{ IL = L_{1} \cup \cdots \cup L_{n} }[/math]. A mapping [math]\displaystyle{ \varphi: \; V \rightarrow IL }[/math] is a list coloring, if [math]\displaystyle{ \varphi }[/math] is a proper coloring and [math]\displaystyle{ \varphi(v_{i}) \in L_{i} }[/math] holds for all [math]\displaystyle{ 1 \leq i \leq n }[/math].

See also

• List chromatic number.