|
Записки научных семинаров ПОМИ, 2016, том 450, страницы 37–42
(Mi znsl6335)
|
|
|
|
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)
Оценка динамического хроматического числа графа через его хроматическое число
Н. Ю. Власоваa, Д. В. Карповba a С.-Петербургский государственный университет, Университетский пр. 28, Старый Петергоф, 198504, Санкт-Петербург, Россия
b С.-Петербургское отделение Математического института
им. В. А. Стеклова РАН, Фонтанка 27, 191023 С.-Петербург
Аннотация:
Раскраска вершин графа называется динамической, если в окрестности любой вершины степени не менее 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\ge3$ и $\Delta(G)\ge3$ – более сильное неравенство $\chi_2(G)\le kc$. Библ. – 9 назв.
Ключевые слова:
хроматическое число, правильная раскраска, динамическая раскраска.
Поступило: 11.10.2016
Образец цитирования:
Н. Ю. Власова, Д. В. Карпов, “Оценка динамического хроматического числа графа через его хроматическое число”, Комбинаторика и теория графов. VIII, Зап. научн. сем. ПОМИ, 450, ПОМИ, СПб., 2016, 37–42; J. Math. Sci. (N. Y.), 232:1 (2018), 21–24
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/znsl6335 https://www.mathnet.ru/rus/znsl/v450/p37
|
Статистика просмотров: |
Страница аннотации: | 147 | PDF полного текста: | 39 | Список литературы: | 29 |
|