Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2411.17885 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909622785277952 |
|---|---|
| author | Botler, F. Couto, Y. S. Fernandes, C. G. de Figueiredo, E. F. Gómez, R. Santos, V. F. dos Sato, C. M. |
| author_facet | Botler, F. Couto, Y. S. Fernandes, C. G. de Figueiredo, E. F. Gómez, R. Santos, V. F. dos Sato, C. M. |
| contents | Chernyshev, Rauch, and Rautenbach proved that every connected graph on $n$ vertices with less than $\frac{11}{5}n-\frac{18}{5}$ edges has a vertex cut that induces a forest, and conjectured that the same remains true if the graph has less than $3n-6$ edges. We improve their result by proving that every connected graph on $n$ vertices with less than $\frac{9}{4}n$ edges has a vertex cut that induces a forest. We also study weaker versions of the problem that might lead to an improvement on the bound obtained. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_17885 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Extremal Problems on Forest Cuts and Acyclic Neighborhoods in Sparse Graphs Botler, F. Couto, Y. S. Fernandes, C. G. de Figueiredo, E. F. Gómez, R. Santos, V. F. dos Sato, C. M. Combinatorics Discrete Mathematics Chernyshev, Rauch, and Rautenbach proved that every connected graph on $n$ vertices with less than $\frac{11}{5}n-\frac{18}{5}$ edges has a vertex cut that induces a forest, and conjectured that the same remains true if the graph has less than $3n-6$ edges. We improve their result by proving that every connected graph on $n$ vertices with less than $\frac{9}{4}n$ edges has a vertex cut that induces a forest. We also study weaker versions of the problem that might lead to an improvement on the bound obtained. |
| title | Extremal Problems on Forest Cuts and Acyclic Neighborhoods in Sparse Graphs |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2411.17885 |