|
Записки научных семинаров ПОМИ, 2010, том 381, страницы 47–77
(Mi znsl3852)
|
|
|
|
Эта публикация цитируется в 6 научных статьях (всего в 6 статьях)
Динамические правильные раскраски вершин графа
Д. В. Карпов Санкт-Петербургское отделение Математического института им. В. А. Стеклова РАН, С-Петербург, Россия
Аннотация:
Назовем подразбиением полного графа $K_n$ любой граф, который можно получить заменой нескольких ребер $K_n$ на цепочки длины 2 (с каждой такой цепочкой добавляется новая вершина степени 2).
Пусть $G$ – связный простой граф с максимальной степенью вершин $d\ge8$. В работе доказывается, что динамическая правильная раскраска вершин графа $G$ в $d$ цветов существует тогда и только тогда, когда $G$ отличен от $K_{d+1}$ и его подразбиений. Библ. – 7 назв.
Ключевые слова:
правильная раскраска, динамическая раскраска, теорема Брукса.
Поступило: 29.10.2010
Образец цитирования:
Д. В. Карпов, “Динамические правильные раскраски вершин графа”, Комбинаторика и теория графов. II, Зап. научн. сем. ПОМИ, 381, ПОМИ, СПб., 2010, 47–77; J. Math. Sci. (N. Y.), 179:5 (2011), 601–615
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/znsl3852 https://www.mathnet.ru/rus/znsl/v381/p47
|
Статистика просмотров: |
Страница аннотации: | 405 | PDF полного текста: | 135 | Список литературы: | 51 |
|