Раскраска

Раскраска (Coloring, colouring) — для некоторого графа [math]\displaystyle{ \,G }[/math] и натурального числа [math]\displaystyle{ \,k }[/math] функция вида [math]\displaystyle{ f: \, V(G) \rightarrow \{1,2,...,k\} }[/math], отображающая множество вершин в множество цветов. Иногда, чтобы подчеркнуть мощность множества цветов, говорят о вершинной [math]\displaystyle{ \,k }[/math]-раскраске или просто о [math]\displaystyle{ \,k }[/math]-раскраске. Интерес представляют только те раскраски, при которых смежные вершины окрашиваются в различные цвета. Такие раскраски называются правильными. Поскольку функция [math]\displaystyle{ \,f }[/math] не обязательно сюръективна, при [math]\displaystyle{ \,k }[/math]-раскраске фактически может быть использовано менее [math]\displaystyle{ \,k }[/math] цветов. Таким образом, правильную [math]\displaystyle{ \,k }[/math]-раскраску графа [math]\displaystyle{ \,G }[/math] можно рассматривать как разбиение множества вершин на не более чем [math]\displaystyle{ \,k }[/math] непустых классов, каждый из которых является независимым множеством.

Задача выяснения, является ли данный неориентированный граф [math]\displaystyle{ \,k }[/math]-раскрашиваемым, является [math]\displaystyle{ \mathcal NP }[/math]-полной. Она остается [math]\displaystyle{ \mathcal NP }[/math]-полной даже при фиксированном [math]\displaystyle{ \,k=3 }[/math].

См. также

• Ациклическая раскраска,
• Полная раскраска,
• Последовательная раскраска,
• Правильная раскраска,
• Реберная [math]\displaystyle{ \,k }[/math]-раскраска.

Литература

• Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.