Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
Динамические правильные раскраски вершин графа. / Карпов, Д.В.
в: ЗАПИСКИ НАУЧНЫХ СЕМИНАРОВ САНКТ-ПЕТЕРБУРГСКОГО ОТДЕЛЕНИЯ МАТЕМАТИЧЕСКОГО ИНСТИТУТА ИМ. В.А. СТЕКЛОВА РАН, Том 381, 2010, стр. 47-77.Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
}
TY - JOUR
T1 - Динамические правильные раскраски вершин графа.
AU - Карпов, Д.В.
PY - 2010
Y1 - 2010
N2 - Назовем подразбиением полного графа $K_n$ любой граф, который можно получить заменой нескольких ребер $K_n$ на цепочки длины 2 (с каждой такой цепочкой добавляется новая вершина степени 2). Пусть $G$ -- связный простой граф с максимальной степенью вершин $d\ge 8$. В работе доказывается, что динамическая правильная раскраска вершин графа $G$ в $d$ цветов существует тогда и только тогда, когда $G$ отличен от $K_{d+1}$ и его подразбиений.
AB - Назовем подразбиением полного графа $K_n$ любой граф, который можно получить заменой нескольких ребер $K_n$ на цепочки длины 2 (с каждой такой цепочкой добавляется новая вершина степени 2). Пусть $G$ -- связный простой граф с максимальной степенью вершин $d\ge 8$. В работе доказывается, что динамическая правильная раскраска вершин графа $G$ в $d$ цветов существует тогда и только тогда, когда $G$ отличен от $K_{d+1}$ и его подразбиений.
KW - правильная раскраска
KW - динамическая раскраска
KW - теорема Брукса [proper coloring
KW - dynamic coloring
KW - Brooks' theorem]
M3 - статья
VL - 381
SP - 47
EP - 77
JO - ЗАПИСКИ НАУЧНЫХ СЕМИНАРОВ САНКТ-ПЕТЕРБУРГСКОГО ОТДЕЛЕНИЯ МАТЕМАТИЧЕСКОГО ИНСТИТУТА ИМ. В.А. СТЕКЛОВА РАН
JF - ЗАПИСКИ НАУЧНЫХ СЕМИНАРОВ САНКТ-ПЕТЕРБУРГСКОГО ОТДЕЛЕНИЯ МАТЕМАТИЧЕСКОГО ИНСТИТУТА ИМ. В.А. СТЕКЛОВА РАН
SN - 0373-2703
ER -
ID: 5250003