RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. POMI, 2017 Volume 464, Pages 26–47 (Mi znsl6520)

This article is cited in 3 papers

Decomposition of a $2$-connected graph into three connected subgraphs

D. V. Karpovab

a St. Petersburg Department of Steklov Mathematical Institute of Russian Academy of Sciences, St. Petersburg, Russia
b St. Petersburg State University, St. Petersburg, Russia

Abstract: Let $G$ be a $2$-connected graph on $n$ vertices such that any its $2$-vertex cutset splits $G$ into at most three parts and $n_1+n_2 +n_3=n$. We prove that there exists a decomposition of the vertex set of $G$ into three disjoint subsets $V_1$, $V_2$, $V_3$, such that $|V_i|=n_i$ and the induced subgraph $G(V_i)$ is connected for each $i$.

Key words and phrases: $2$-connected graph, decomposition, Györi–Lovász theorem.

UDC: 519.173.1

Received: 22.11.2017


 English version:
Journal of Mathematical Sciences (New York), 2019, 236:5, 490–502


© Steklov Math. Inst. of RAS, 2024