Хроматическое число и хроматическая функция графа

18. Вершинами графа перестановок являются перестановки n чисел {1, 2, 3, ×××, n}. Вершины, отличающиеся транспозицией, содединяются ребрами. Будет ли граф перестановок плоским при n≥3? Найти хроматическое число графа перестановок чисел {1, 2, 3, ×××, n}.

19. Булев куб B_n размерности n состоит из вершин (e₁ , e₂ , × × ×, e_n ), e_i Î{0, 1}, где две вершины смежны если они отличаются одной компонентой e_i . Найти хроматическое число графа B_n.

20. Найти хроматическую функцию графа A_n:

21. Найти хроматическую функцию полного графа K_n.

22. Найти хроматический многочлен графа, изображением которого является буква ‘A’.

23. Найти хроматический многочлен графа C₅.

Ответ: f(q) = q⁵ – 5q⁴ + 10q³ – 10q² + 4q

24. Найти хроматические многочлены и хроматические числа графов

25. Соседние области флага имеют различные цвета. Сколькими способами можно раскрасить в семь цветов изображенный ниже флаг?

26. Соседние области флага должны иметь различные цвета. Сколькими способами можно раскрасить в q цветов флаг:

27. Найти число раскрасок граней куба, при которых соседние грани имеют

различные цвета. Число цветов не превосходит 7.

28. Построить рекуррентное соотношение для хроматических многочленов и найти эти многочлены.

29. Найти хроматическое число графа, полученного удалением одного ребра из полного графа K_n. Двух ребер. Трех ребер, составляющих треугольник.

Ответ: n-1, n-1, n-2.