Изменения
Нет описания правки
# Докажите, что хроматический многочлен дерева равен $t(t-1)^{n - 1}$.
# Докажите, что если хроматический многочлен графа равен $t(t-1)^{n - 1}$, то граф является деревом.
# Приведите пример двух связных графов, которые не являются деревьями, не являются изоморфными и имеют одинаковые хроматические многочлены.
# Докажите, что если длина максимального простого нечетного цикла в $G$ есть $k$, то $\chi(G)\le k + 1$.
# Если степени вершин графа $G$ равны $d_1 \ge d_2 \ge \ldots \ge d_n$, то $\chi(G)\le \max\min\{i, d_i+1\}$.
# Доказать формулу Зыкова для хроматического многочлена графа $G$: $P_G(x)=\sum\limits_{i=1}^n pt(G,i)x^{\underline{i}}$, где $pt(G,i)$ — число способов разбить вершины $G$ на $i$ независимых множеств.
# Доказать формулу Уитни: пусть $G$ - обыкновенный $(n, m)$ - граф. Тогда коэффициент при $x^i$, где $1\le i\le n$ в хроматическом многочлене $P_G(x)$ равен $\sum \limits_{j=0}^{m}{(-1)^jN(i, j)}$, где $N(i, j)$ - число остовных подграфов графа $G$, имеющих $i$ компонент связности и $j$ рёбер.
# Граф называется однозначно раскрашиваемым, если любые две его раскраски в $\chi(G)$ цветов совпадают с точностью до переименования цветов. Приведите пример однозначно раскрашиваемого графа и графа, который не является однозначно раскрашиваемым
# Какое минимальное число вершин может быть в однозначно раскрашиваемом в 3 цвета графе, отличном от полного графа?
# Какое минимальное число ребер может быть в однозначно раскрашиваемом в $k$ цветов графе с $n$ вершинами?
