"Записки научных семинаров ПОМИ"
Том 450 , стр. 37-42
Оценка динамического хроматического числа графа через его хроматическое число
Н. Ю. Власова, Д. В. Карпов
С.-Петербургский государственный университет,
Университетский пр. 28, Старый Петергоф,
198504, Санкт-Петербург, Россия
evropa2100@mail.ru
С.-Петербургское отделение Математического института
им. В А. Стеклова РАН, Фонтанка 27,
191023 С.-Петербург;
С.-Петербургский государственный университет,
Университетский пр. 28, Старый Петергоф,
198504, Санкт-Петербург, Россия
dvk0@yandex.ru
- Аннотация:
Раскраска вершин графа называется {\em динамической}, если в окрестности любой вершины степени не менее 2 представлены хотя бы 2 разных цвета. По аналогии с хроматическим числом $\chi(G)$ графа $G$ определяются его динамическое число $\chi_d(G)$ (минимальное число цветов в динамической раскраске) и динамическое хроматическое число $\chi_2(G)$ (минимальное число цветов в правильной динамической раскраске). В работе доказано, что $\chi_2(G)\le \chi(G)\cdot \chi_d(G)$ и построена бесконечная серия примеров графов, для которых эта оценка на $\chi_2(G)$ точна.
Для графа $G$ положим $k=\lceil \frac{2\Delta(G)}{\delta(G)} \rceil$. В работе доказано, что $\chi_2(G)\le (k+1)c$, а при $k\ge 3$ и $\Delta(G)\ge 3$ --- более сильное неравенство $\chi_2(G)\le kc$.
Библ. -- 9 назв.
- Ключевые слова: хроматическое число, правильная раскраска, динамическая раскраска
[chromatic number, proper coloring, dynamic coloring]
Полный текст(.pdf)