Extremal Problems on Forest Cuts and Acyclic Neighborhoods in Sparse Graphs

2024/11/26 by Fábio Botler, Botler, F., Yan S. Couto +11 · 4 citations
Computer Science · Engineering · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Packing Problems

paper · pdf · doi:10.48550/arxiv.2411.17885

openalex publication_date 2024/11/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Chernyshev, Rauch, and Rautenbach proved that every connected graph on n vertices with less than (11)/(5)n-(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 (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.

Cited by

• Degenerate Vertex Cuts in Sparse Graphs
• Cyclic Neighborhoods in Digraphs
• On cuts of small chromatic number in sparse graphs
• Sharp thresholds for NAC-colourings and stable cuts in random graphs

Related

• Forest Cuts in Sparse Graphs
• On forest and bipartite cuts in sparse graphs
• Number of Edges in 3-Connected Graphs with Cyclic Neighborhoods
• Sparse graphs with an independent or foresty minimum vertex cut
• Decomposition of Sparse Graphs into Forests: The Nine Dragon Tree Conjecture for k ≤ 2