Хроматическое число графа
$\gamma(G)$ - минимальное кол-во цветов которыми можно раскрасить граф
Оценки хроматического числа графа
$G(V,E)$ - граф
$\rho(G)$ - размер максимальной клики графа
$$\gamma(G) \ge \rho(G)$$
$\alpha(G)$ - кол-во вершин в максимально независиммом множестве
$$\gamma(G) \ge \frac{|V|}{\alpha(G)}$$
$\Delta(G) = \underset{{v_{i} \in V}}{\max} |\Gamma(v_{i})|$ - максимальная степень вершины графа
$$\gamma(G)\ge \frac{\Delta(G)+1}{2}$$
$\lambda_{max},\lambda_{min}$ - минимальные и макс собственные значения от [[Eigen Decomposition]] матрицы смежности от графа $A$
$$\gamma(G)\ge 1+ \frac{\lambda_{max}}{|\lambda_{min}|}$$
