2019/10/03 by Shimon Kogan, Kogan, Shimon
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1910.01356
openalex publication_date 2019/10/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For a graph G, let a(G) denote the maximum size of a subset of vertices that induces a forest. We prove the following. 1. Let G be a graph of order n, maximum degree Δ>0 and maximum clique size ω. Then a(G) ≥ (6n)/(2Δ+ ω+2). This bound is sharp for cliques. 2. Let G=(V,E) be a triangle-free graph and let d(v) denote the degree of v ∈ V. Then a(G) ≥ ∑v ∈ V min(1, (3)/(d(v)+2) ). As a corollary we have that a triangle-free graph G of order n, with m edges and average degree d ≥ 2 satisfies a(G) ≥ (3n)/(d+2). This improves the lower bound n - (m)/(4) of Alon-Mubayi-Thomas for graphs of average degree greater than 4. Furthermore it improves the lower bound (20n - 5m - 5)/(19) of Shi-Xu for (connected) graphs of average degree at least (9)/(2).