Презентация, доклад на тему Связь хроматического числа и степенной последовательности графа

мостах
Гипотеза четырех красок 1878 г. – А. Кэли Формулировка гипотезы 1976 г. – К. Аппель и В. Хейкен Компьютерное доказательство гипотезы
Нахождение хроматического числа графа – нерешенная в настоящее время задача

степенной последовательности графа;
2) получить формулу для оценки или определения хроматического числа графа, у которого в степенной последовательности только одно повторяющееся, не более трех раз, значение.

никакие две смежные вершины не получают одинакового цвета.

Две различные раскраски одного графа
в 6 цветов (слева) и 4 цвета (справа)

цвета (слева) и колеса с 5 вершинами в 3 цвета (справа)

n содержит ровно два одинаковых значения и значения 1 и n – 1. В таком графе степени вершин – это числа 1, 2, …, n – 1 причем среди них ровно два повторяются. Задача исследования заключается в нахождении формулы хроматического числа таких графов.

n содержит ровно три одинаковых значения и значения 1 и n – 1. В таком графе степени вершин – это числа 1, 2, …, n – 1 причем среди них ровно три повторяются, а одно отсутствует в последовательности. Задача исследования заключается в нахождении формулы хроматического числа таких графов.

и от повторяющейся степени k

эти вершины

программы "Шаг в будущее". – 2013. – Т. 16. – С. 81 – 83.