Вершинная и реберная раскраска графа

Пусть Sn — множество целых чисел от 1 до п, которые мы будем называть цветами; n-раскраской графа G назовем такое отображение множества V(G) в Sn, при котором вершины, являющиеся концами одного ребра, окрашиваются в разные цвета (т.е. таким вершинам сопоставляются разные элементы из Sn). Через N(G;n) обозначим число n-раскрасок графа G. Очевидно, что N(G;n) является графовой функцией. Ясно также, что если G имеет петли, то N(G;n)=0.

Введение: 2
Глава I. Вершинная раскраска графа 4
1.1 Основные понятия вершинной раскраски графа. 4
1.2 Переборный алгоритм для раскраски 13
Глава II. Реберная раскраска графа 15
2.1 Раскрытие понятия правильной реберной раскраски графа. 15
2.2 Методы реберной раскраски графа 16
Литература 22