Хроматическое число

ХРОМАТИЧЕСКОЕ ЧИСЛО [chromatic number] — число, характеризующее количество несмежных вершин графа. Если пометить все вершины графа р цветами (отсюда и термин“хроматическое”) и при этом никакие две смежные вершины не будут окрашены одинаково, то такой граф называется хроматическим порядка р Минимальное число р, при котором граф является хроматическим порядка р, называется хроматическим числом данного графа. Оно находится с помощью аналитического метода, основанного на приемах линейного программирования.