Раскраска графа

Раскра́ска гра́фа, приписывание цветов вершинам и (или) рёбрам графа, обладающее определёнными свойствами. Правильная вершинная (рёберная) раскраска – это раскраска вершин (рёбер) графа, при которой любые смежные вершины (рёбра) окрашены в разные цвета. Правильную вершинную раскраску часто называют просто раскраской графа. Граф называется ${\displaystyle k}$-раскрашиваемым, если существует правильная вершинная раскраска графа ${\displaystyle k}$ цветами. Наименьшее число цветов, достаточное для правильной вершинной раскраски графа ${\displaystyle G}$, называется хроматическим числом ${\displaystyle \chi (G)}$ графа ${\displaystyle G}$. Если ${\displaystyle \chi (G)=k}$, то граф ${\displaystyle G}$ называется ${\displaystyle k}$-хроматическим. Граф является ${\displaystyle 2}$-хроматическим тогда и только тогда, когда он не содержит простых циклов нечётной длины. Если максимальная степень вершин графа ${\displaystyle G}$ равна ${\displaystyle r}$, то граф ${\displaystyle G}$ всегда ${\displaystyle r}$-раскрашиваем, за исключением двух случаев: 1) ${\displaystyle r=2}$ и ${\displaystyle G}$ имеет компоненту связности, являющуюся циклом нечётной длины; 2) ${\displaystyle r>2}$ и полный граф с ${\displaystyle r+1}$ вершинами является компонентой связности графа ${\displaystyle G}$.

Для объединения двух графов ${\displaystyle G_{1}}$ и ${\displaystyle G_{1}}$ справедливо неравенство

${\displaystyle \chi (G_{1}\cup G_{2})\leqslant \chi (G_{1})\chi (G_{2})}$,

причём равенство здесь достигается. Более того, если граф ${\displaystyle G}$ такой, что ${\displaystyle \chi (G)=k=ab}$, то найдутся подграфы ${\displaystyle G_{1}}$ и ${\displaystyle G_{2}}$ в ${\displaystyle G}$ такие, что ${\displaystyle G=G_{1}\cup G_{2}}$, ${\displaystyle \chi (G_{1})=a}$, ${\displaystyle \chi (G_{2})=b}$. Если ${\displaystyle G}$ – граф с ${\displaystyle n}$ вершинами и ${\displaystyle {\overline {G}}}$ – граф, дополнительный к ${\displaystyle G}$, то

${\displaystyle 2{\sqrt {n}}\leqslant \chi (G)+\chi ({\overline {G}})\leqslant n+1}$
${\displaystyle n\leqslant \chi (G)\chi ({\overline {G}})\leqslant \left({\frac {n+1}{2}}\right)^{2},}$

причём все границы достигаются. Хроматическим числом ${\displaystyle \chi (S)}$ двумерной поверхности ${\displaystyle S}$ называется максимум хроматических чисел графов, допускающих правильную укладку на ${\displaystyle S}$. Для ориентируемой поверхности ${\displaystyle S_{\gamma }}$ рода ${\displaystyle \gamma >0}$ справедливо равенство

${\displaystyle \chi (S_{\gamma })=\left[{\frac {7+{\sqrt {1+48\gamma }}}{2}}\right]}$.

При ${\displaystyle \gamma =0}$ это равенство принимает вид ${\displaystyle \chi (S_{0})=4}$, что составляет утверждение задачи четырёх красок. Пусть ${\displaystyle f(G,t)}$ – число различных правильных раскрасок графа ${\displaystyle G}$ с нумерованными вершинами в ${\displaystyle t}$ или меньше цветов, тогда для любого графа ${\displaystyle G}$ функция ${\displaystyle f(G,t)}$ есть многочлен от переменной ${\displaystyle t}$, называемый хроматичеcким многочленом графа ${\displaystyle G}$. Например, хроматический многочлен любого дерева с ${\displaystyle n}$ вершинами имеет вид ${\displaystyle f(G,t)=t(t-1)^{n-1}}$. Рёберное хроматическое число (хроматический класс) ${\displaystyle \chi '(G)}$ графа ${\displaystyle G}$ – это наименьшее число цветов, достаточное для правильной раскраски рёбер графа G. Если максимальная степень вершин графа ${\displaystyle G}$ равна ${\displaystyle k}$ (допускаются кратные рёбра), то

${\displaystyle k\leqslant \chi '(G)\leqslant \left[{\frac {3}{2}}k\right]}$.

Если при этом кратность каждого ребра не более ${\displaystyle r}$, то ${\displaystyle \chi '(G)\leqslant k+r}$. В частности, для графов без петель и кратных рёбер ${\displaystyle 1\leqslant \chi '(G)\leqslant k+1}$.

Задачи на раскраски графа возникают при проектировании коммуникаций, в радиоэлектронике, в планировании эксперимента и других областях.