Давайте немного ослабим раскраску, то есть позволим небольшому количеству смежных вершин присваивать один и тот же цвет. Монохроматический компонент определяется как связанный компонент в подграфе, индуцированный набором вершин, которые получают один и тот же цвет, и вопрос заключается в том, чтобы задать минимальное количество цветов необходимое для раскраски графа, чтобы наибольший монохроматический компонент имел размер не более чем C .
В этом случае традиционную раскраску можно рассматривать как -окрашивание. Следовательно, найти минимальное число λ NP-трудно для плоского графа вообще.
Мой вопрос: как насчет -окрашивания планарных графов или, в более общем смысле, -окрашивания для C ≥ 2 ?
Это можно рассматривать как двойственную задачу о том , что изучается Эдвардс и Фарра , где фиксируется, и один просят найти минимальный размер C .