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 -