New results on large induced forests in graphs

arXiv1910.01356MaRDI QIDQ6326461FDOQ6326461

Authors: Shimon Kogan 

Publication date: 3 October 2019

Abstract: 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 $Delta>0$ and maximum clique size $omega$. Then [ a(G) geq frac{6n}{2Delta + omega +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 $vinV$. Then [ a(G) geq sum_{v in V} minleft(1, frac{3}{d(v)+2} ight). ] As a corollary we have that a triangle-free graph $G$ of order $n$, with $m$ edges and average degree $dgeq2$ satisfies [ a(G) geq frac{3n}{d+2}. ] This improves the lower bound $n-fracm4$ of Alon-Mubayi-Thomas for graphs of average degree greater than $4$. Furthermore it improves the lower bound $frac20n-5m-519$ of Shi-Xu for (connected) graphs of average degree at least $frac92$.

This page was built for publication: New results on large induced forests in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6326461)