List chromatic number

Материал из WEGA
Версия от 16:14, 31 мая 2011; Glk (обсуждение | вклад) (Новая страница: «'''List chromatic number''' --- предписанное хроматическое число. The '''list chromatic number''' <math>l\chi(G)</math> of the graph …»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

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.