Курсовая работа: О раскрасках графов

Содержание

• Введение

Мы будем работать с неориентированными графами без петель и крат-ных рёбер и называть их просто графами. Если разрешены кратные рёб-ра, мы будем говорить о мультиграфе, но петли всё равно будут запре-щены. Как обычно, для вершины v ∈ V (G) мы будем обозначать через N_G(v) окрестность вершины v, то есть множество вершин, смежных с ней; через ∆(G) и δ(G) мы будем обозначать соответственно максималь-ную и минимальную степень вершины графа G.

В этой работе мы попытаемся обобщить теорему Брукса [1], утвер-ждающую, что для любого натурального ∆ 3 и для любого графа
G без подграфов вида K_∆+1, имеющего ∆(G) ∆, верно χ(G) ∆, на f-динамические раскраски — модификацию динамических раскрасок, предложенных Монтгомери в [2].

Определение 1. Пусть f : N₀ → N₀ — частичная функция. Раскраску графа G будем называть f-динамической, если для каждого p ∈ Dom f верно следующее: у каждой вершины v ∈ V (G), имеющей степень deg v p, в её окрестности имеются вершины хотя бы f(p) различных цветов.
Через χ_f (G) будем обозначать f-хроматическое число графа G, то

есть наименьшее натуральное m такое, что G имеет правильную f-динамическую раскраску в m цветов, или правильную f-динамическую m-раскраску
(или +∞, если такого числа m не существует).

Будем говорить, что G списочно f-раскрашиваем в m цветов, если для любого назначения вершинам G списков цветов из некоторой па-литры P существует правильная f -динамическая P-раскраска G, в ко-торой каждая вершина покрашена в некоторый цвет из её списка. Че-рез ch_f (G) будем обозначать списочное f-хроматическое число графа G, то есть наименьшее натуральное m такое, что G является списочно f-раскрашиваемым в m цветов (или +∞, если такого числа m не суще-ствует).

Мы будем через {(p₁, c₁), (p₂, c₂), . . . , (p_q, c_q)} обозначать частичную функцию, для каждого i отображающую p_i в c_i. В частности,

• ∅-динамическая раскраска — это просто раскраска (соответствую-щее хроматическое и списочное хроматическое число обозначаются
χ(G) и ch(G));



3