Неправильная плоская окраска с размером монохроматического компонента

11

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

Мой вопрос: как насчет -окрашивания планарных графов[λ,2] или, в более общем смысле, -окрашивания для C 2 ?[λ,C]C2

Это можно рассматривать как двойственную задачу о том , что изучается Эдвардс и Фарра , где фиксируется, и один просят найти минимальный размер C .λС

Исин Цао
источник

Ответы:

3

2-раскрашенное идеальное сопоставление в кубических планарных графах очень похоже на вашу задачу, которая была сформулирована как NP-полная Шефером в его знаменитой работе с теоремой о дихотомии, хотя он не дал доказательства для кубических плоских графов. Задача требует существования двух раскрасок кубических плоских графов так, что каждая вершина имеет ровно одного соседа того же цвета, что и она сама.

РЕДАКТИРОВАТЬ: Неисправная окраска является версией решения вашей проблемы. Граф является (k, d) -цветным, если можно закрасить вершины k цветами так, чтобы ни одна вершина не была смежной с более чем d вершинами такого же цвета. Было показано, что решение задачи (2,1) - окрашивание с дефектами, что эквивалентно вашей задаче оптимизации, является NP-полным даже для плоских графов.

Мухаммед Аль-Туркистани
источник
Что такое редукция от «2-раскрашенного идеального соответствия в кубических плоских графах» к проблеме Исина?
2-цветное идеальное сопоставление - это особый случай, когда максимальный размер связанного компонента точно равен C.
Мухаммед Аль-Туркистани
Спасибо за ваш ответ, но я не могу согласиться с вами. Как и в задаче «2-цветное идеальное соответствие в кубических плоских графах», КАЖДЫЙ компонент должен быть ровно 2. Но мой вопрос кажется проще.
Исинь Цао
Да, я пропустил эту разницу.
Мухаммед Аль-Туркистани