Теория графов

Здравствуйте, Сергей!

Я выложил файл с теоретической справкой по графам, включая запрошеные Вами базы и клики в центре дистанционного образования ДонНТУ в курсе ОДМ:
http://dist.donntu.edu.ua/course/view.php?id=11

Кодовое слово для записи на курс: okodove

Вопрос связанный с раскраской графов.
Существует ли какая-либо связь с планарностью графа и минимальным, максимальным (вобщем - достаточным) числом цветов для раскраска этого графа?
Ведь планарный граф с числом вершин более 4-х, может иметь клику только на 4-х вершинах, не больше. Значит, в общем случае, для планарного графа (>4-х вершин) минимальное число цветов равно 4-ре. А как быть с максимальным? И вообще, какие свойства планарного и не планарного графов могут влиять на минимальное число цветов?

HUKTO,

Вот, например, возьмем максимально полный двудольный граф на 10 вершинах (доли 5:5). Его можно раскрасить в 2 цвета, но по-моему, он не планарный! Вот я теперь не знаю, что в лабораторной писать HUKTO, форумы popoff.donetsk.ua

Представьте себе две кучки графов: в одной лежат все планарные графы, а в другой - все не планарные. У Вас также есть набор из 4 красок. В теореме о 4 красках сказано, что в первой кучке Вы можете покрасить своими 4 красками любой граф. В этой теореме ничего, совсем ничего не сказано о том, что Вы можете покрасить или не покрасить из второй кучки. Единственный вывод, который Вы можете сделать из факта существования теоремы - это то, что, видимо, во второй кучке существует хотя бы один граф, для покраски которого Ваших 4 красок будет недостаточно.

Если граф не планарный, то для его покраски достаточно 4 цветов. Обратное не верно. Если граф можно покрасить в 4 (или меньше) цветов, то это не означает, что граф - не планарный.