14. Правильные вершинные раскраски графов, хроматическое число, неравенства для хроматического числа.

Определение. Графом G называется пара (V, E), где – непустое множество вершин графа, а– множество ребер графа, причем каждое ребро – это неупорядоченная пара различных вершин.

Определение. Говорят, что вершины графа G правильно раскрашены с помощью цветов {c₁, c₂,…, c_r}, если каждой вершине поставлен в соответствие некоторый цвет, причем любым двум смежным вершинам соответствуют разные цвета.

Утверждение 1. Для правильной раскраски вершин любого двудольного графа достаточно двух цветов.

Определение. Хроматическим числом графа называется минимальное число красок, достаточное для правильной раскраски его вершин.

Хроматическое число графа G далее будем обозначать через χ(G). Выполняются следующие свойства хроматического числа:

1. ;

2. если G – двудольный граф, то ;

3. если Т – дерево, то (так как всякое дерево – двудольный граф);

4. если G – планарный граф, то .

Утверждение 2. Для любого графа G справедлива верхняя оценка , гдеd = max deg(v).

Определение. Хроматическим многочленом графа G называется многочлен P(G,x), который при каждом целом неотрицательном значении х равен количеству различных способов правильной раскраски вершин графа G с использованием не более х фиксированных цветов.