On forest and bipartite cuts in sparse graphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908381828087808 |
|---|---|
| author | Bogdanov, Ilya I. Neustroeva, Elizaveta Sokolov, Georgy Volostnov, Alexei Russkin, Nikolay Voronov, Vsevolod |
| author_facet | Bogdanov, Ilya I. Neustroeva, Elizaveta Sokolov, Georgy Volostnov, Alexei Russkin, Nikolay Voronov, Vsevolod |
| contents | The paper is devoted to sufficient conditions for the existence of vertex cuts in simple graphs, where the induced subgraph on the cut vertices belongs to a specified graph class. In particular, we show that any connected graph with $n$ vertices and fewer than $(19n - 28)/8$ edges admits a forest cut. This result improves upon recent bounds, although it does not resolve the conjecture that the sharp threshold is $3n - 6$ (Chernyshev, Rauch, Rautenbach, 2024). Furthermore, we prove that if the number of edges is less than $(80n-134)/31$, then the graph admits a bipartite cut. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_16179 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On forest and bipartite cuts in sparse graphs Bogdanov, Ilya I. Neustroeva, Elizaveta Sokolov, Georgy Volostnov, Alexei Russkin, Nikolay Voronov, Vsevolod Combinatorics 05C35, 05C40 The paper is devoted to sufficient conditions for the existence of vertex cuts in simple graphs, where the induced subgraph on the cut vertices belongs to a specified graph class. In particular, we show that any connected graph with $n$ vertices and fewer than $(19n - 28)/8$ edges admits a forest cut. This result improves upon recent bounds, although it does not resolve the conjecture that the sharp threshold is $3n - 6$ (Chernyshev, Rauch, Rautenbach, 2024). Furthermore, we prove that if the number of edges is less than $(80n-134)/31$, then the graph admits a bipartite cut. |
| title | On forest and bipartite cuts in sparse graphs |
| topic | Combinatorics 05C35, 05C40 |
| url | https://arxiv.org/abs/2505.16179 |