K-Choosable graph

Материал из WikiGrapp

[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.

Литература

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