List chromatic number

Материал из WEGA

List chromatic number --- предписанное хроматическое число.

The list chromatic number [math]\displaystyle{ l\chi(G) }[/math] of the graph [math]\displaystyle{ G }[/math] is the smallest [math]\displaystyle{ k }[/math] such that whenever each vertex [math]\displaystyle{ v \in V(G) }[/math] is assigned a list [math]\displaystyle{ \Phi(v) }[/math] of [math]\displaystyle{ k }[/math] admissible colours, there exists such a proper colouring [math]\displaystyle{ f }[/math] of [math]\displaystyle{ V(G) }[/math] that each vertex [math]\displaystyle{ v }[/math] is coloured by a colour [math]\displaystyle{ f(v) \in \Phi(v) }[/math]. The list edge chromatic number [math]\displaystyle{ le\chi(G) }[/math] is defined analogously. We can also say that [math]\displaystyle{ le\chi(G) }[/math] is the list chromatic number of the line graph [math]\displaystyle{ L(G) }[/math]. Other names are Prescribed chromatic number, Choice number, Choosability.