





























We show that every graph $G$ of maximum degree $Δ$ and sufficiently large order has a vertex cutset $S$ of order at most $Δ$ that induces a subgraph $G[S]$ of maximum degree at most $Δ-3$. For $Δ\in \{ 4,5\}$, we refine this result by considering also the average degree of $G[S]$. If $G$ has no $K_{r,r}$ subgraph, then we show the existence of a vertex cutset that induces a subgraph of maximum degree at most $\left(1-\frac{1}{r\choose 2}\right)Δ+O(1)$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。