Графа Раскраска

- приписывание цветов вершинам и (или) ребрам графа, обладающее определенными свойствами. Правильная вершинная (реберная) раскраска - это раскраска вершин (ребер) графа, при к-рой любые смежные вершины (ребра) окрашены в разные цвета. Правильную вершинную раскраску часто наз. Просто раскраской графа. Граф наз. K-pаскрашиваемым, если существует правильная вершинная Г. P. Kцветами. Наименьшее число цветов, достаточное для правильной вершинной раскраски графа G, наз. Хроматическим числом графа G. Если , то граф Gназ. K- хроматическим. Граф является 2-хроматическим тогда и только тогда, когда он не содержит простых циклов нечетной длины. Если максимальная степень вершин графа Gравна г, то граф Gвсегда r-раскрашиваем, за исключением двух случаев.

1) r=2 и G имеет компоненту связности, являющуюся циклом нечетной длины. 2) r>2 и полный граф с r+1 вершинами является компонентой связности графа G. Для объединения двух графов н справедливо неравенство причем равенство здесь достигается. Более того, если граф G такой, что , то найдутся подграфы и в G такие, что , Если G - граф с пвершинами н - граф, дополнительный к G, то причем все границы достигаются. Хроматическим числом двумерной поверхности Sназ. Максимум хроматич. Чисел графов, допускающих правильную укладку на S(см. Графа укладка). Для ориентируемой поверхности рода справедливо равенство При это равенство принимает вид , что составляет утверждение четырех красок задачи.

Пусть - число различных правильных раскрасок графа G с нумерованными вершинами в tили меньше цветов, тогда для любого графа G функция есть многочлен от переменной t, наз. Хроматическим многочленом графа G. Напр., хроматич. Многочлен любого дерева с пвершинами имеет вид . Реберное хроматич. Число (хроматический класс) графа G-это наименьшее число цветов, достаточное для правильной раскраски ребер графа G. Если максимальная степень вершин графа G равна k(допускаются кратные ребра), то Если при этом кратность каждого ребра не более r, то В частности, для графов без петель и кратных ребер . Задачи на Г. Р. Возникают при проектировании коммуникаций, в радиоэлектронике, в планировании эксперимента н других областях.

Лит.:[1] Xарари Ф., Теория графов, пер. С англ." М., 1973. [2] Оре О., Теория графов, пер. С англ., М., 1968. [3] Шеннон К. Э., "Кибернетический сборник", 1960, в. 2, с. 249-53. В. Б. Алексеев.