Forest cuts in sparse graphs
We consider the conjecture that every graph G of order n with less than 3 n − 6 edges has a vertex cut that induces a forest. Maximal planar graphs do not have such vertex cuts and show that the density condition would be best possible. We verify the conjecture for planar graphs and show that every graph G of order n with less than 11 5 n − 18 5 edges has a vertex cut that induces a forest.
Authors
- Dieter Rautenbach (ORCID: https://orcid.org/0000-0002-7214-042X)
- Johannes Rauch (ORCID: https://orcid.org/0000-0002-6925-8830)
- Vsevolod Chernyshev
Institutions
- Centre National de la Recherche Scientifique (FR)
- Universität Ulm (DE)
- University of Clermont Auvergne (FR)
- Clermont Université (FR)
- Technische Hochschule Ulm (DE)
Publication Details
- Journal
- Discrete Mathematics
- Published
- 2025-05-27
- DOI
- https://doi.org/10.1016/j.disc.2025.114594
- Citations
- 2
- Primary Topic
- Advanced Graph Theory Research
- Type
- article
- Field-Weighted Citation Impact
- 3.01