"Записки научных семинаров ПОМИ"
Том 464, стр. 26-47
Разбиение двусвязного графа на три связных подграфа
Д. В. Карпов
С.-Петербургское отделение
Математического института
им. В А. Стеклова РАН,
Фонтанка 27, 191023 С.-Петербург;
С.-Петербургский государственный университет,
Университетский пр. 28, Старый Петергоф,
198504 Санкт-Петербург, Россия
dvk0@yandex.ru
- Аннотация:
Пусть $G$ -- двусвязный граф на $n$ вершинах такой, что каждое его
двухэлементное разделяющее множество разбивает $G$ не более чем на 3
части, а $n_1+n_2 +n_3=n$. В работе доказано, что существует разбиение
множества вершин графа $G$ на такие непересекающиеся подмножества $V_1$,
$V_2$, $V_3$, что $|V_i|=n_i$ и индуцированный подграф~$G(V_i)$ связен
для каждого $i$.
Библ. -- 9 назв.
- Ключевые слова: двусвязный граф, разбиение, теорема Дьори-Ловаса
[2-connected graph, decomposition, Gy\"ori-Lov\'asz theorem]
Полный текст(.pdf)