K-Choosable graph

Материал из WEGA
Перейти к навигации Перейти к поиску

[math]\displaystyle{ k }[/math]-Choosable graph --- [math]\displaystyle{ k }[/math]-выбираемый граф.

1. A graph [math]\displaystyle{ G }[/math] is [math]\displaystyle{ k }[/math]-choosable if its list chromatic number satisfies the inequality [math]\displaystyle{ \chi_{\ell} (G) \leq k }[/math].

2. A graph [math]\displaystyle{ G }[/math] is [math]\displaystyle{ k }[/math]-choosable if, whenever each vertex [math]\displaystyle{ v }[/math] is given a list (set) [math]\displaystyle{ L(v) }[/math] of [math]\displaystyle{ k }[/math] colours, [math]\displaystyle{ G }[/math] has a proper colouring in which each vertex receives a colour from its own list.