У меня есть исторический вопрос.
Я пытаюсь определить ссылку на тот факт, что 3-окрашиваемость графиков (альтернативно, окрашиваемость для заданного k \ geq 3 ) является NP-трудной.
Заманчивым ответом является «оригинальная статья Карпа», но это не так. Вот сканирование: сводимость среди комбинаторных проблем, Карп (1972) . Это доказывает, что хроматическое число (вход: граф. Выход: ) является сложным. Это более сложная проблема, и сокращение отличается от стандартной конструкции гаджета (с 3 цветами: True, False и Ground), которая подразумевает твердость 3-цветности.
Garey and Johnson, Computer and intractability , имеют окрашиваемость как [GT4] и ссылаются на Karp (1972).
np-hardness
ho.history-overview
Тор Хусфельдт
источник
источник
Ответы:
László Lovász , « Покрытия и раскраски гиперграфов» , Материалы четвертой Юго-Восточной конференции по комбинаторике, теории графов и вычислительной технике, Utilitas Math., Winnipeg, Man., 1973, pp. 3–12, доказали, что хроматическое число уменьшается до 3- colourability.
Я думаю, что это первое доказательство NP-полноты 3-окрашиваемости.
Вот бумага Ловаша; см. также превосходное объяснение Вашека Чваталя сокращению Ловаша.
источник
Вот еще одна статья 1973 года, которая доказывает, что 3-цветность NP-трудна.
(Похоже, что Ловаш и Стокмейер получили свои результаты независимо друг от друга.)
Обновление: см. Комментарии ниже.
источник