Пусть дан неориентированный граф G=(V,X).
Определение: Раскраскойвершин графа называется сопоставление (приписывание) цветов вершинам графа.
Определение: Раскраска называется правильной, если смежные вершины окрашены в разные цвета.
Определение: Наименьшее число цветов, необходимых для правильной раскраски? называется хроматическимчисломи обозначается χ(G).
Определение: Неориентированный граф G называется бихроматическим, если χ (G)=2
Примеры:
1) G: χ (G)=2
2) χ (Km,n)=2
Теорема: Для того, чтобы граф, содержащий хотя бы одно ребро, был бихроматическим, необходимо и достаточно, чтобы он не содержал элементарных циклов нечетной длины.
В полном графе Kn любые две различные вершины связаны ребром? Gj’njve χ (Kn) = n
Определение: Множество вершин, окрашенных в один цвет, называется одноцветнымклассом.
