Раскраски графов и многочлены

Если в графе степень каждой вершины не превосходит $d$, то его можно правильно раскрасить в $d+1$ цвет.

Если в связном графе степень каждой вершины не превосходит $d$ и есть вершина степени менее $d$, то его можно правильно раскрасить в $d$ цветов.

Если в связном графе степень каждой вершины не превосходит $d$ и есть вершина, после удаления которой граф перестаёт быть связным, то граф можно правильно раскрасить в $d$ цветов.

Если связный граф, имеющий более двух вершин, при удалении некоторого ребра распадается на два графа, каждый из которых можно правильно раскрасить в $d$ цветов, то и исходный граф можно правильно раскрасить в $d$ цветов.

В связном графе степень каждой вершины не превосходит трёх. Известно, что его можно правильно раскрасить в 3 цвета так, чтобы соседи некоторой вершины были одного цвета. Добавили одну вершину и выходящие из неё рёбра так, что по-прежнему степени всех вершин не превосходят трёх. Докажите, что полученный граф можно правильно раскрасить в 3 цвета.

В связном графе степень каждой вершины не превосходит трёх. Известно, что его можно правильно раскрасить в 3 цвета и при любой такой раскраске у каждой вершины есть соседи разных цветов. Добавили одну вершину и выходящие из неё рёбра так, что по-прежнему степени всех вершин не превосходят трёх и полученный граф отличен от $K_{4}$. Докажите, что полученный граф можно правильно раскрасить в 3 цвета.

Теорема Брукса. Если степень каждой вершины графа не превосходит $d \geq 3$ и нет $(d+1)$-клики, то граф можно правильно раскрасить в $d$ цветов.

Если граф невозможно правильно раскрасить в $k-1$ цвет, то для любой его правильной раскраски в $k$ цветов существует путь, в котором встречается ровно по одной вершине каждого цвета.

Если максимальный из путей в графе, проходящих по каждой своей вершине только один раз, проходит через $d$ вершин, то граф можно правильно раскрасить в $d$ цветов.

Если максимальный нечётный несамопересекающийся цикл в графе проходит через $d-1$ вершину, то граф можно правильно раскрасить в $d$ цветов.

Если степень каждой вершины графа не превосходит $d$, то рёбра графа можно правильно раскрасить в $d+1$ цвет.

Существует такая раскраска рёбер графа $K_{m,n}$ в два цвета, что число одноцветных подграфов $K_{a,b}$ не больше $\binom {m}{a}\binom {n}{b}2^{1-ab}$.

На какое число может измениться хроматическое число графа, если добавить к графу одно ребро? Или, формально, найдите все целые $k$, для которых существует граф $G$ и его ребро $u$ такие, что $\chi (G) - \chi (G-u) = k$.

$\chi (V, E_{1} \cup E_{2}) \leq \chi (V, E_{1})\chi (V, E_{2})$. (Напомним, что через $(V, E)$ обозначается граф со множеством вершин $V$ и множеством рёбер $E$.)

Для любых $r_{1}, r_{2} \in \mathbb {N}$ постройте такие графы $(V, E_{1})$ и $(V, E_{2})$, что $\chi (V, E_{1} \cup E_{2}) = \chi (V, E_{1})\chi (V, E_{2})$, $\chi (V, E_{1}) = r_{1}$ и $\chi (V, E_{2}) = r_{2}$.

Вершины произвольного графа $G$ можно занумеровать так, чтобы жадный алгоритм его раскраски использовал ровно $\chi (G)$ цветов.

Для каждого целого $k > 0$ постройте такие двудольный граф и нумерацию его вершин, что раскраска графа, построенная жадным алгоритмом, отвечающим построенной нумерации, имеет не менее $k$ цветов.

полного графа;

графа, не имеющего рёбер;

пути;

цикла;

дерева

$\chi_{G} = \chi_{G-u} - \chi_{G/u}$ для любого ребра $u$ графа $G$.

Теорема Биркгофа—Уитни. Для каждого графа $G$ существует ровно один такой многочлен, что для любого $t$ число $\chi_{G}(t)$ правильных раскрасок графа $G$ в $t$ цветов равно значению в точке $t$ этого многочлена.

Степень хроматического многочлена $\chi_{G}$ равна $n$, старший коэффициент равен 1, второй коэффициент равен $(-e)$, коэффициенты знакопеременны (т.е. коэффициент при $t^{n-2k}$ неотрицателен и коэффициент при $t^{n-2k+1}$ неположителен для любого целого $k$).

Третий коэффициент хроматического многочлена графа, считая с самого старшего, однозначно определяется набором подграфов графа, содержащих 3 вершины.

Число $\left|\chi_{G}(-1)\right|$ равно числу ациклических ориентаций графа $G$, т.е. числу способов так расставить стрелки на его рёбрах, чтобы полученный ориентированный граф не содержал ориентированных циклов.

Если хроматический многочлен графа равен $t(t-1)^{n-1}$, то граф --- дерево.

Не существует графа с хроматическим многочленом $t^{4} - 3t^{3} + 3t^{2}$.

Путь из $m$ вершин «прицепили» за один из концов к одной из вершин графа $G$, содержащего $n$ вершин. Выразите хроматический многочлен полученного графа с $m+n-1$ вершиной через $\chi_{G}$.

Если $H, K$ --- графы, на которые распадается связный граф $G$ при удалении его ребра, то $t\chi_{G} = (t-1)\chi_{H}\chi_{K}$.

Функция $\chi_{G}'$ является многочленом от $t$.

Старший моном в $\chi_{G}'$ равен $t^{e}$.

Коэффициент при $t^{e-1}$ в $\chi_{G}'$ равен $-\sum_{v \in V(G)} \binom {\deg v}{2}$.

остовных лесов в графе $G$ (т.е. объединений остовов его компонент);

таких наборов рёбер графа $G$, что для любой компоненты связности графа лежащие в ней рёбра из набора образуют связный подграф;

подграфов графа $G$, являющихся лесами.

число из п. (1) задачи 3.3.6;

число из п. (2) задачи 3.3.6;

число из п. (3) задачи 3.3.6;

хроматический многочлен.