Можем ли мы раскрасить граф в три цвета за полиномиальное время, если мы знаем, что этот граф раскрашивается в три цвета?

Я понимаю, что решить, является ли граф трехцветным, сложно с точки зрения NP. Но мне интересно, когда нам дан гарантированный трехцветный граф, можем ли мы раскрасить его в три цвета за полиномиальное время? Большинство ресурсов, которые я нашел, говорят о том, чтобы решить, можно ли раскрасить график в 3 цвета... Я не уверен, какие ключевые слова я должен ввести в Google, чтобы получить лучший результат поиска... Итак, я здесь. Любая помощь будет принята с благодарностью.


graph algorithm math graph-coloring
person user3695760    schedule 18.11.2015    source источник
comment
Если бы мы могли, мы бы решили NP-сложную задачу за полиномиальное время. Просто запустите полиномиальный алгоритм во время подсчета операций. Если предел превышен, граф не раскрашивается в 3 цвета.   -  person n. 1.8e9-where's-my-share m.    schedule 18.11.2015
comment
Спасибо! Это имеет смысл....   -  person user3695760    schedule 18.11.2015

Ответы (1)


arrow_upward
2
arrow_downward

Поискав в Интернете, я нашел эту статью. Его авторы доказывают, что раскрасить 3-раскрашиваемый граф в 4 цвета NP-сложно. Этот результат переносится на 3-раскрашиваемые графы ограниченной степени.

Поскольку вы размышляли о подходящем поисковом выражении Google, мое было

how to 3-color a 3-colorable graph
person collapsar    schedule 21.11.2015