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