Sparse Vertex Cutsets and the Maximum Degree
We show that every graph $G$ of maximum degree $\Delta$ and sufficiently large order has a vertex cutset $S$ of order at most $\Delta$ that induces a subgraph $G[S]$ of maximum degree at most $\Delta-3$. For $\Delta\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 $\Big(1-\frac{1}{{r\choose 2}}\Big)\Delta+O(1)$.
Authors
- Dieter Rautenbach (ORCID: https://orcid.org/0000-0002-7214-042X)
- Stéphane Bessy (ORCID: https://orcid.org/0000-0001-7130-4990)
- Johannes Rauch (ORCID: https://orcid.org/0000-0002-6925-8830)
- Uéverton S. Souza (ORCID: https://orcid.org/0000-0002-5320-9209)
Publication Details
- Journal
- The Electronic Journal of Combinatorics
- Published
- 2025-05-22
- DOI
- https://doi.org/10.37236/12902
- Primary Topic
- Advanced Numerical Analysis Techniques
- Type
- article
- Field-Weighted Citation Impact
- 0.00