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

- приписывание цветов вершинам и (или) ребрам графа, обладающее определенными свойствами. Правильная вершинная (реберная) раскраска - это раскраска вершин (ребер) графа, при к-рой любые смежные вершины (ребра) окрашены в разные цвета. Правильную вершинную раскраску часто наз. просто раскраской графа. Граф наз. k-pаскрашиваемым, если существует правильная вершинная Г. p. kцветами. Наименьшее число цветов, достаточное для правильной вершинной раскраски графа G, наз. хроматическим числом [img: http://localhost:8080/file/010429-31.jpg] графа G. Если [img: http://localhost:8080/file/010429-32.jpg], то граф Gназ. k- хроматическим. Граф является 2-хроматическим тогда и только тогда, когда он не содержит простых циклов нечетной длины. Если максимальная степень вершин графа Gравна г, то граф Gвсегда r-раскрашиваем, за исключением двух случаев: 1) r=2 и G имеет компоненту связности, являющуюся циклом нечетной длины; 2) r>2 и полный граф с r+1 вершинами является компонентой связности графа G. Для объединения двух графов [img: http://localhost:8080/file/010429-33.jpg] н [img: http://localhost:8080/file/010429-34.jpg] справедливо неравенство [img: http://localhost:8080/file/010429-35.jpg] причем равенство здесь достигается. Более того, если граф G такой, что [img: http://localhost:8080/file/010429-36.jpg], то найдутся подграфы [img: http://localhost:8080/file/010429-37.jpg] и [img: http://localhost:8080/file/010429-38.jpg] в G такие, что [img: http://localhost:8080/file/010429-39.jpg], [img: http://localhost:8080/file/010429-40.jpg] Если G - граф с пвершинами н [img: http://localhost:8080/file/010429-41.jpg] - граф, дополнительный к G, то [img: http://localhost:8080/file/010429-42.jpg] причем все границы достигаются. Хроматическим числом [img: http://localhost:8080/file/010429-43.jpg] двумерной поверхности Sназ. максимум хроматич. чисел графов, допускающих правильную укладку на S(см. Графа укладка). Для ориентируемой поверхности [img: http://localhost:8080/file/010429-44.jpg] рода [img: http://localhost:8080/file/010429-45.jpg] справедливо равенство [img: http://localhost:8080/file/010429-46.jpg] При [img: http://localhost:8080/file/010429-47.jpg] это равенство принимает вид [img: http://localhost:8080/file/010429-48.jpg], что составляет утверждение четырех красок задачи. Пусть [img: http://localhost:8080/file/010429-49.jpg] - число различных правильных раскрасок графа G с нумерованными вершинами в tили меньше цветов, тогда для любого графа G функция [img: http://localhost:8080/file/010429-50.jpg] есть многочлен от переменной t, наз. хроматическим многочленом графа G. Напр., хроматич. многочлен любого дерева с пвершинами имеет вид [img: http://localhost:8080/file/010429-51.jpg] [img: http://localhost:8080/file/010429-52.jpg]. Реберное хроматич. число (хроматический класс) [img: http://localhost:8080/file/010429-53.jpg] графа G-это наименьшее число цветов, достаточное для правильной раскраски ребер графа G. Если максимальная степень вершин графа G равна k(допускаются кратные ребра), то [img: http://localhost:8080/file/010429-54.jpg] Если при этом кратность каждого ребра не более r, то [img: http://localhost:8080/file/010429-55.jpg] В частности, для графов без петель и кратных ребер [img: http://localhost:8080/file/010429-56.jpg]. Задачи на Г. р. возникают при проектировании коммуникаций, в радиоэлектронике, в планировании эксперимента н других областях.