Раскраска графов. Теорема о пяти красках. Гипотеза четырех красок

Хроматическое число графа G — минимальное число цветов, в которые можно раскрасить вершины графа G так, чтобы концы любого ребра имели разные цвета. Обозначается χ(G).

Если наибольшая из степеней вершин графа равна Р, то этот граф Р+1 -раскрашиваем.

K-раскрашиваемый граф — граф, хроматическое число которого не превосходит K. То есть его вершины можно раскрасить K разными цветами так, что у любого ребра концы будут разного цвета.

K-хроматический граф — граф, хроматическое число которого равно K. То есть вершины графа можно раскрасить K цветами так, что у любого ребра концы будут разного цвета, но так раскрасить K − 1 цветами — уже нельзя.

Билет 11