RUS  ENG
Полная версия
ЖУРНАЛЫ // Записки научных семинаров ПОМИ // Архив

Зап. научн. сем. ПОМИ, 2017, том 464, страницы 26–47 (Mi znsl6520)

Эта публикация цитируется в 3 статьях

Разбиение двусвязного графа на три связных подграфа

Д. В. Карповab

a С.-Петербургское отделение Математического института им. В. А. Стеклова РАН, Фонтанка 27, 191023 С.-Петербург, Россия
b С.-Петербургский государственный университет, Университетский пр. 28, Старый Петергоф, 198504 Санкт-Петербург, Россия

Аннотация: Пусть $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 назв.

Ключевые слова: двусвязный граф, разбиение, теорема Дьори–Ловаса.

УДК: 519.173.1

Поступило: 22.11.2017


 Англоязычная версия: Journal of Mathematical Sciences (New York), 2019, 236:5, 490–502


© МИАН, 2024