Раскраски графов

Докажите, что граф $k$-раскрашиваем тогда и только тогда, когда каждый его блок $k$-раскрашиваем.

Покажите, что любой планарный граф 6-раскрашиваем.

Покажите, что любой планарный граф 5-раскрашиваем.

Докажите теорему 9.1: $\chi (G) \leq \Delta (G)+1$ для любого графа $G$.

Покажите, что для любого графа $G$, $\chi (G) \leq 1+\max \delta \left(G^{\prime }\right)$, где максимум берётся по всем порождённым подграфам $G^{\prime }$ графа $G$.

Докажите теорему 2 (теорему Брукса): если $G$ — связный граф, не являющийся ни полным графом, ни нечётным циклом, $\chi (G) \leq \Delta (G)$.

Докажите, что если множество вершин $V=\left\{ v_{1}, v_{2}, \ldots , v_{n}\right\}$ графа $G$ имеет невозрастающую последовательность степеней $d_{1} \geq d_{2} \geq \ldots \geq d_{n}$, то $\chi (G) \leq \max_{i} \min \left\{ d_{i}+1, i\right\}$.

Покажите, что число цветов, необходимых для раскраски вершин $G$ методом «сначала наибольшая степень», не превышает $1+\Delta (G)$.

Используйте алгоритм «сначала наибольшая степень» для раскраски вершин графа, изображённого на рис. 9-10.

$k$-хроматический граф $G$ называется критически $k$-хроматическим (или $k$-критическим), если $\chi (G-v)= k-1$ для каждой вершины $\nu$ графа $G$. Покажите, что критически $k$-хроматический граф $G$ является блоком.

Приведите пример $k$-хроматического графа, не являющегося критически $k$-хроматическим.

Охарактеризуйте критически $k$-хроматические графы при $k=2$ и $k=3$.

$k$-хроматический граф $G$ называется минимально $k$-хроматическим, если $\chi (G-e)=k-1$ для каждого ребра $e$ графа $G$. Приведите пример:

Покажите, что $k$-хроматический граф содержит критически (минимально) $k$-хроматический граф.

Покажите, что если $G$ критически $k$-хроматичен, $\delta (G) \geq (k-1)$. Приведите контрпример, показывающий, что обратное неверно.

Приведите пример $k$-хроматического графа $G$, для которого неравенство $\delta (G) \geq (k-1)$ не выполняется.

Докажите, что $k$-хроматический граф $G$ имеет по меньшей мере $k$ вершин степени не менее $k-1$.

Используйте неравенство, полученное в задаче 9.15, для доказательства теоремы Секереша—Уилфа (задача 9.51).

Докажите, что критически $k$-хроматический граф $G$ ровно с одной вершиной, степень которой превышает $(k-1)$, минимально $k$-хроматичен.

Покажите, что если $G=(V, E)$ — граф с $\chi (G) \geq k$ и с разбиением вершин $(X, Y)$ множества $V$, таким что порождённые $X$ и $Y$ подграфы $G(X)$ и $G(Y)$ соответственно $(k-1)$-раскрашиваемы, разрез $[X, Y]$, состоящий из рёбер $E$, соединяющих вершины из $X$ и вершины из $Y$, содержит не менее $(k-1)$ рёбер.

Покажите, что критически $k$-хроматический граф $G$ является $(k-1)$-рёберно связным. [Эквивалентно, любой связный минимально $k$-хроматический граф $(k-1)$-рёберно связен.] Приведите пример, показывающий, что обратное неверно.

Покажите, что если $G$ — критически $k$-хроматический граф, не существует подграфов $G_{1}$ и $G_{2}$, таких что $G=G_{1} \cup G_{2}$ и одновременно $G_{1} \cap G_{2}$ полон.

Покажите, что подграф, порождённый разделяющим множеством $W$ вершин критически $k$-хроматического графа, не является полным графом. В частности, если $\left|W\right|=2$, две вершины в $W$ не смежны.

Приведите пример графа $G$ с разделяющим множеством $W$, состоящим из двух смежных вершин.

Если минимально $k$-хроматический граф $G$ имеет разделяющее множество $W$, состоящее из двух вершин $u$ и $v$, покажите, что:

Проиллюстрируйте теорему Дирака на примере графа, изображённого на рис. 9-13(a).

Покажите, что если минимально $k$-хроматический граф имеет разделяющее множество, состоящее из двух вершин, сумма их степеней не менее $(3 k-5)$.

Используйте неравенство, полученное в задаче 9.27, для доказательства того, что $\chi (G) \leq \Delta (G)$, где $G$ — связный граф, не являющийся ни полным графом, ни нечётным циклом, в частном случае, когда $G$ не 3-связен. (Это часть теоремы Брукса.)

$k$-хроматический граф $G$ называется однозначно раскрашиваемым, если любая $k$-раскраска $G$ порождает одно и то же разбиение множества вершин $G$.

Покажите, что если $k$-хроматический граф $G$ однозначно раскрашиваем, подграф, порождённый объединением любых двух множеств разбиения вершин при раскраске, является связным графом.

Покажите, что если $k$-хроматический граф $G$ однозначно раскрашиваем, он $(k-1)$-связен.

Покажите, что любой 4-хроматический однозначно раскрашиваемый планарный граф $G$ является максимальным планарным графом.

Покажите, что граф, полученный из не содержащего треугольников $k$-хроматического графа методом Мыцельского, является не содержащим треугольников $(k+1)$-хроматическим графом.

Найдите $P(G, x)$, где $G$ — циклический граф с $n$ вершинами, где $n=3$ или $n=4$.

Если $e$ — ребро графа $K_{4}$, найдите хроматический многочлен графа $K_{4}-e$.

Покажите, что если $G$ — объединение двух графов, $G_{1}$ и $G_{2}$, имеющих ровно одну общую вершину, хроматический многочлен $G$ равен произведению хроматических многочленов $G_{1}$ и $G_{2}$, делённому на $x$.

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

Получите хроматический многочлен графа, изображённого на рис. 9-15.

Fig. 9-15

Покажите, что если $G$ — граф порядка $n$ и размера $m$, абсолютная величина коэффициента при $x^{n-1}$ в хроматическом многочлене равна размеру графа.

Покажите, что граф порядка $n$ является деревом тогда и только тогда, когда его хроматический многочлен равен $x(x-1)^{n-1}$.

Используйте теорему редукции, доказанную в задаче 9.41, чтобы вычислить $P(G, x)$ графа $G$ из задачи 9.38.

Хроматический многочлен циклического графа порядка $n$ равен $(x-1)^{n}+(-1)^{n}(x-1)$.

Докажите, что сумма коэффициентов хроматического многочлена графа, имеющего по меньшей мере одно ребро, равна 0.

Покажите, что коэффициенты хроматического многочлена чередуются по знаку.

Покажите, что если $P(G, x)=x^{n}-a_{n-1} x^{n-1}+a_{n-2} x^{n-2}-a_{n-3} x^{n-3}+\cdots$ — хроматический многочлен связного графа $G$, то $1<a_{n-1}<a_{n-2}<\cdots <a_{r}$, где $r$ — целая часть $(n / 2+1)$.

Покажите, что если $P(G, x)=x^{n}-a_{n-1} x^{n-1}+a_{n-2} x^{n-2}-a_{n-3} x^{n-3}+\cdots$ — хроматический многочлен связного графа $G$, то $a_{i} \geq \binom { n-1}{r-1}$ для каждого $i$.

Покажите, что коэффициент при $x$ в хроматическом многочлене связного графа не равен нулю.

Покажите, что наименьшее число $k$, такое что коэффициент при $x^{k}$ в хроматическом многочлене $G$ не равен нулю, равно числу компонент.

Покажите, что $x^{5}-7 x^{4}+9 x^{3}-3 x^{2}$ не может быть хроматическим многочленом простого графа.

Необходимые условия, которым должен удовлетворять хроматический многочлен связного простого графа порядка $n$ и размера $m(m>0)$: (1) он должен быть многочленом от $x$ степени $n$, (2) он унитарный (приведённый) многочлен, (3) сумма коэффициентов равна нулю, (4) коэффициенты чередуются по знаку, (5) свободный член равен нулю, (6) коэффициент при $x$ не равен нулю, (7) коэффициент при $x^{n-1}$ равен $-m$, и (8) абсолютные величины коэффициентов при $x^{n}, x^{n-1}, x^{n-2}, \ldots , x^{r}$ строго возрастают, где $r$ — целая часть $(n / 2+1)$. Приведите пример многочлена, удовлетворяющего этим восьми условиям, но не являющегося хроматическим многочленом простого связного графа.

Покажите, что если $G$ — двудольный мультиграф, его хроматический индекс равен $\Delta (G)$. В частности, покажите, что хроматический индекс полного двудольного графа $K_{m, n}$ равен максимуму из $\left\{ m, n\right\}$.

Если аспирант кафедры прослушал $k$ курсов $(k \geq 0)$, преподаваемых профессором этой кафедры, профессор должен принять у студента $k$ устных экзаменов в конце учебного года. Каждый устный экзамен длится ровно $t$ часов. Найдите минимальное время, необходимое для завершения всех кафедральных устных экзаменов, если известно число курсов, прослушанных каждым студентом у каждого профессора.

Латинским квадратом порядка $n$ называется матрица $n \times n$ с элементами из множества $\left\{ 1,2, \ldots , n\right\}$, такая что ни один элемент не встречается дважды в одной строке и ни один элемент не встречается дважды в одном столбце. Покажите, что латинский квадрат порядка $n$ можно построить с помощью $n$-рёберной раскраски полного двудольного графа $K_{n, n}$.

Покажите, что если $G$ — полный граф с $2 n$ вершинами, его хроматический индекс равен $2 n-1$.

Покажите, что если $G$ — полный граф с $2 n-1$ вершинами, его хроматический индекс равен $2 n-1$.

В пансионе живёт $2 n$ школьниц. Каждое утро они идут в школу группами по двое, парами. Найдите максимальное число последовательных утренних прогулок, которое они могут совершить так, чтобы каждая девочка составила пару с каждой другой девочкой ровно один раз за эти прогулки.

В пансионе живут 15 девочек, которые ходят в школу группами по трое (тройками) все семь дней недели. Возможно ли составить тройки так, чтобы никакие две девочки не гуляли вместе более одного раза?

Докажите теорему 9.4 (теорему Визинга): хроматический индекс простого графа $G$ равен либо $\Delta (G)$, либо $\Delta (G)+1$.

Если $G$ — $r$-регулярный простой граф с нечётным числом вершин, покажите, что его хроматический индекс равен $r+1$. Верно ли обратное?

Пусть $G$ — 3-раскрашиваемый кубический граф, рёбра которого раскрашены цветами $c_{i}(i=1,2,3)$, и пусть $F$ — разрезающее множество в $G$. Если число рёбер цвета $c_{i}$ в $F$ равно $x_{i}$, покажите, что три числа, $x_{1}, x_{2}$ и $x_{3}$, либо все чётны, либо все нечётны.

Докажите теорему 9.5: если кубический граф имеет мост, его хроматический индекс равен 4.

Пусть $G^{\prime }$ — граф, полученный из кубического графа $G$ стягиванием треугольника (цикла из трёх вершин) в единственную вершину. Покажите, что $\chi^{\prime }(G)=3$ тогда и только тогда, когда $\chi^{\prime }\left(G^{\prime }\right)=3$.

Пусть $e_{1}$ и $e_{2}$ — два ребра без общей вершины в кубическом графе $G$. Вставим две вершины $x_{1}$ и $y_{1}$ на $e_{1}$ и две вершины $x_{2}$ и $y_{2}$ на $e_{2}$. Соединим $x_{1}$ и $x_{2}$ ребром. Соединим $y_{1}$ и $y_{2}$ ребром. Если хроматический индекс построенного таким образом нового графа $G^{\prime }$ равен 4, покажите, что хроматический индекс $G$ также равен 4.

Приведите контрпример, показывающий, что хроматический индекс $G^{\prime }$ (из задачи 9.64) не обязан быть равен 4, когда хроматический индекс $G$ равен 4.

Пусть $G$ — кубический граф с разрезающим множеством $F$, состоящим из трёх рёбер $e_{i}(i=1,2,3)$, соединяющих вершины $u_{i}$ и $v_{i}$, где все шесть вершин различны, так что $G-F$ имеет два подграфа, $H_{1}$ и $H_{2}$. Построим вершину $u$ в $H_{1}$ и соединим её с тремя концевыми вершинами разрезающего множества в $H_{1}$, создав новый кубический граф $G_{1}$. Аналогично построим другой кубический граф $G_{2}$, введя вершину $\nu$ и соединив её с концевыми вершинами разрезающего множества в $H_{2}$. Покажите, что граф $G$ 3-рёберно раскрашиваем тогда и только тогда, когда оба графа, $G_{1}$ и $G_{2}$, 3-рёберно раскрашиваемы.

Пусть $G$ — кубический граф без мостов с разрезающим множеством $F$, состоящим из двух рёбер: ребра $e_{1}$, соединяющего $u_{1}$ и $v_{1}$, и ребра $e_{2}$, соединяющего $u_{2}$ и $v_{2}$, так что $G-F$ имеет две компоненты, $H_{1}$ и $H_{2}$. Пусть $u_{1}$ и $u_{2}$ находятся в одной компоненте. Соединим $u_{1}$ и $u_{2}$ ребром в $H_{1}$, создав кубический (муль­ти)граф $G_{1}$. Аналогично построим $G_{2}$ из $H_{2}$, соединив $v_{1}$ и $v_{2}$. Покажите, что граф $G$ 3-рёберно раскрашиваем тогда и только тогда, когда оба графа, $G_{1}$ и $G_{2}$, 3-рёберно раскрашиваемы.

Разрезающее множество $F$ графа $G$ называется циклическим разрезающим множеством, если $G-F$ имеет две компоненты, каждая из которых содержит цикл. Циклической рёберной связностью $\boldsymbol {\lambda }_{\boldsymbol {c}}(\boldsymbol {G})$ графа $G$ называется мощность наименьшего циклического разрезающего множества в $G$, и $G$ называется циклически $k$-рёберно связным, если $\lambda_{c}(G) \geq k$. Покажите, что граф Петерсена циклически 4-рёберно связен.

Снарком по определению называется нераскрашиваемый, циклически 4-рёберно связный кубический граф обхвата не менее 5. Покажите, что это определение более ограничительно в том смысле, что кубический граф без мостов нельзя назвать снарком лишь потому, что он нераскрашиваем. (Гипотеза об обхвате — это утверждение о том, что у каждого снарка есть цикл, состоящий из пяти или шести рёбер. Сейчас известно, что эта гипотеза ложна.)

Пусть $x$ и $y$ — произвольные смежные вершины кубического графа $G$ порядка $n$, где $x$ смежна также с $a$ и $b$. Аналогично $y$ смежна с $c$ и $d$. Предполагается, что четыре вершины, $a, b, c$ и $d$, различны. Пусть $e$ и $f$ — два независимых ребра кубического графа $G^{\prime }$ порядка $n^{\prime }$, где $e$ соединяет вершины $p$ и $q$, а $f$ соединяет вершины $r$ и $s$. Удалим $x$ и $y$ в $G$ и удалим $e$ и $f$ из $G^{\prime }$. Затем соединим два графа, построив четыре новых ребра, соединяющих $a$ и $p$, $b$ и $q$, $c$ и $r$, а также $d$ и $s$. Построенный таким образом граф называется точечным произведением $\boldsymbol {G}. \boldsymbol {G}^{\prime }$ этих двух графов, и он, очевидно, является кубическим графом порядка $n+n^{\prime }-$ 2. Покажите, что точечное произведение двух снарков является снарком.

Снарком Блануши называется точечное произведение графа Петерсена с самим собой. Постройте снарк Блануши.

Fig. 9-19

Покажите, что снарк не является гамильтоновым графом.

Приведите пример негамильтонова кубического графа, не являющегося снарком.

Приведите пример «неснарка» — циклически 4-связного непланарного кубического графа, рёбра которого можно раскрасить тремя цветами.

Покажите, что в любой кубической карте есть по меньшей мере одна область, граница которой содержит менее шести рёбер. (См. также решённую задачу 8.16.)

Покажите, что существует неизбежное множество из четырёх конфигураций, и перечислите их.

Покажите, что первые три графа, изображённые на рис. 9-22, приводимы.

(Неизбежное множество Вернике) Покажите, что множество, состоящее из пяти графов, изображённых на рис. 9-23, является неизбежным.

Fig. 9-23

Покажите, что бриллиант Биркгофа (см. рис. 9-24) приводим.

Fig. 9-24

Коэффициентом потока цикла $C$ в ориентации $D$ графа $G$ называется отношение $p / q$ (где $p \geq q \geq 0$ ), где $p$ — число дуг в одном направлении, а $q$ — число дуг в противоположном направлении в $C$. Покажите, что вершины графа $G$ можно $k$-раскрасить тогда и только тогда, когда существует такая ориентация $D$ графа, при которой коэффициент потока ни одного цикла не превышает $(k-1)$.

Гипотеза Хайоша утверждает, что у каждого $k$-хроматического графа есть подграф, гомеоморфный полному графу порядка $k$. Покажите, что гипотеза верна при $k \leq 4$.

Покажите, что если гипотеза Хайоша верна для $k=5$, теорема о четырёх красках верна.

Покажите, что гипотеза Хайоша ложна при $k \geq 7$.

Гипотеза Хадвигера утверждает, что у каждого $k$-хроматического графа есть подграф, стягиваемый к полному графу порядка $k$.

Докажите, что $\chi \left(S_{g}\right)=H(g)$, где $H(g)$ — целая часть $\frac{1}{2}\left\{ 7+ \sqrt{1+48 g}\right\}$ для любой поверхности положительного рода $g$.

Покажите, что плоский граф $G$ 2-раскрашиваем тогда и только тогда, когда степень каждой области $G$ чётна.

Покажите, что карта 2-раскрашиваема тогда и только тогда, когда она эйлерова.

Плоский граф 3-раскрашиваем тогда и только тогда, когда он является подграфом триангуляции, в которой степень каждой вершины чётна.

Покажите, что:

Числом кликового покрытия $\boldsymbol {\theta }(\boldsymbol {G})$ (также известным как число разбиения) графа $G=(V, E)$ называется минимальное число попарно непересекающихся клик, объединение которых равно множеству $V$. Граф $G$ называется $\boldsymbol {\alpha }$-совершенным, если для каждого порождённого подграфа $H$ графа $G$ $\theta (H)$ равно его числу внутренней устойчивости $\alpha (H)$. Покажите, что граф совершенен тогда и только тогда, когда его дополнение $\alpha$-совершенно.

Покажите, что рёберный граф двудольного графа $G$ совершенен.

Орграф называется транзитивным орграфом, если всякий раз, когда есть дуга из вершины $u$ в вершину $v$ и дуга из $v$ в вершину $w$, есть и дуга из $u$ в $w$. Граф $G$ называется транзитивно ориентируемым графом (также известным как граф сравнимости), если можно сориентировать его рёбра так, чтобы полученный орграф был транзитивным орграфом. Покажите, что граф сравнимости совершенен.

Пусть $W$ — множество вершин связного графа $G=(V, E)$, такое что подграф, порождённый $W$, полон, и такое что $G-W$ — несвязный граф с компонентами $G_{i}=\left(V_{i}, E_{i}\right)$, где $i= 1,2, \ldots , r$. Пусть $H_{i}$ — подграф, порождённый объединением $V_{i}$ и $W$, для каждого $i$. Покажите, что если $\omega \left(H_{i}\right)=\chi \left(H_{i}\right)$ для каждого $i$, то $\omega (G)=\chi (G)$.

Пусть $W$ — множество вершин хордального графа $G$, такое что $W$ — минимальное разделяющее множество. Покажите, что граф, порождённый $W$, полон.

Докажите, что хордальный граф совершенен.

Покажите, что граф совершенен тогда и только тогда, когда каждый порождённый подграф $H$ имеет независимое множество $W$ вершин, такое что $\omega (H-W)<\omega (H)$.

Покажите, что если вершины совершенного графа «заменить» совершенными графами, полученный граф также совершенен.

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

Покажите, что дополнение совершенного графа совершенно.

Покажите, что граф совершенен тогда и только тогда, когда он $\alpha$-совершенен.

(Теорема Эрдёша) Если граф $G=(V, E)$ не содержит $K_{k+1}$ в качестве подграфа, покажите, что существует $k$-хроматический граф $H=(V, F)$, такой что $\operatorname {deg}_{H}(v) \geq \operatorname {deg}_{G}(v)$ для каждой $v$ в $V$. (Говорят, что степени графа $G$ мажорируются графом $H$.)

(Число Турана и граф Турана) Найдите неубывающую последовательность из $k$ натуральных чисел $a_{i}(i= 1,2, \ldots , k)$, сумма которых равна $n$, такую что $\sum_{1 \leq i \leq j<k} a_{i} a_{j}$ максимальна.

Покажите, что если граф $G=(V, E)$ порядка $n$ не содержит $K_{k+1}$ в качестве подграфа, $\left|E\right| \leq t(n, k)$.

Найдите максимальное число рёбер в:

Найдите хроматическое число кубического недвудольного графа.

Покажите, что если $G$ — $k$-критический граф порядка $n$ и размера $m$, $(k-1)(n) \leq 2 m$.

Покажите, что если $k$-хроматический граф $G$ однозначно раскрашиваем, подграф, порождённый объединением любых двух или более подмножеств разбиения вершин, определённого $k$-раскраской, является $(k-1)$-связным.

Покажите, что $\chi (G) \leq 1+n-\alpha (G)$.

Найдите хроматический многочлен $K_{1, n}$.

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

Если $G$ — связный граф порядка $n$, докажите, что $P(G, x) \leq x(x-1)^{n-1}$.

Покажите, что теорема Визинга не обязана быть верна, если рассматриваемый граф не прост.

Покажите, что теорема о четырёх красках верна тогда и только тогда, когда выполняется следующее условие: у каждого планарного графа есть такая ориентация, что коэффициент потока любого цикла в этой ориентации не превышает 3.

Покажите, что гипотеза Хадвигера верна для $k=5$.

Покажите, что любой внешнепланарный граф 3-раскрашиваем.

Покажите, что триангуляция 3-раскрашиваема тогда и только тогда, когда степень каждой её вершины чётна.

Дополнение графа сравнимости называется графом несравнимости. Покажите, что граф несравнимости является и совершенным, и $\alpha$-совершенным.

Покажите, что граф Петерсена несовершенен.

Покажите, что интервальный граф совершенен.

Найдите размер наибольшего: