Хроматическое число и хроматическая функция графа
18. Вершинами графа перестановок являются перестановки n чисел {1, 2, 3, ××× , n}. Вершины, отличающиеся транспозицией, содединяются ребрами. Будет ли граф перестановок плоским при n≥3? Найти хроматическое число графа перестановок чисел {1, 2, 3, ××× , n}.
19. Булев куб Bn размерности n состоит из вершин (e1 , e2 , × × × , en ), ei Î{0, 1}, где две вершины смежны если они отличаются одной компонентой ei . Найти хроматическое число графа Bn .
20. Найти хроматическую функцию графа An:
21. Найти хроматическую функцию полного графа Kn .
22. Найти хроматический многочлен графа, изображением которого является буква ‘A’.
23. Найти хроматический многочлен графа C5 .
Ответ: f(q) = q5 – 5q4 + 10q3 – 10q2 + 4q
24. Найти хроматические многочлены и хроматические числа графов
25. Соседние области флага имеют различные цвета. Сколькими способами можно раскрасить в семь цветов изображенный ниже флаг?
26. Соседние области флага должны иметь различные цвета. Сколькими способами можно раскрасить в q цветов флаг:
| 27. | |
27. Найти число раскрасок граней куба, при которых соседние грани имеют
различные цвета. Число цветов не превосходит 7.
28. Построить рекуррентное соотношение для хроматических многочленов 
и найти эти многочлены.
29. Найти хроматическое число графа, полученного удалением одного ребра из полного графа Kn . Двух ребер. Трех ребер, составляющих треугольник.
Ответ: n-1, n-1, n-2.