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

Для объединения двух графов $G_1$ и $G_1$ справедливо неравенство $$\chi(G_1\cup G_2)\leqslant \chi(G_1)\chi(G_2),$$причём равенство здесь достигается. Более того, если граф $G$ такой, что $\chi(G)=k=ab$, то найдутся подграфы $G_1$ и $G_2$ в $G$ такие, что $G=G_1\cup G_2$, $\chi(G_1)=a$, $\chi(G_2)=b$. Если $G$ – граф с $n$ вершинами и $\overline G$ – граф, дополнительный к $G$, то

$$\begin{gathered} 2\sqrt{n}\leqslant \chi(G)+\chi(\overline G)\leqslant n+1,\\ n\leqslant\chi(G)\chi(\overline G)\leqslant\left(\frac{n+1}2\right)^2, \end{gathered}$$причём все границы достигаются. Хроматическим числом $\chi(S)$ двумерной поверхности $S$ называется максимум хроматических чисел графов, допускающих правильную укладку на $S$. Для ориентируемой поверхности $S_\gamma$ рода $\gamma>0$ справедливо равенство $$\chi(S_\gamma)=\left[\frac{7+\sqrt{1+48\gamma\vphantom{(}}}2\right].$$При $\gamma=0$ это равенство принимает вид $\chi(S_0)=4$, что составляет утверждение задачи четырёх красок. Пусть $f(G, t)$ – число различных правильных раскрасок графа $G$ с нумерованными вершинами в $t$ или меньше цветов, тогда для любого графа $G$ функция $f(G, t)$ есть многочлен от переменной $t$, называемый хроматичеcким многочленом графа $G$. Например, хроматический многочлен любого дерева с $n$ вершинами имеет вид $f(G, t) = t (t – 1)^{n-1}$. Рёберное хроматическое число (хроматический класс) $\chi'(G)$ графа $G$ – это наименьшее число цветов, достаточное для правильной раскраски рёбер графа G. Если максимальная степень вершин графа $G$ равна $k$ (допускаются кратные рёбра), то

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

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