On Large Odd Induced Subgraphs of Graphs

Abstract

For a graph $G$, an odd induced subgraph of $G$ is an induced subgraph in which every vertex has odd degree (within the subgraph). Let $f_o(G)$ denote the maximum size of such a subgraph in $G$. Caro conjectured that there exists a positive constant $c$ such that $f_o(G)≥cn$ for any $n$-vertex graph without isolated vertices, with the best possible value conjectured to be $c=2/7.$ In this paper, improving a recent result of Ferber and Krivelevich, we show that $f_o(G)≥n/1088$ for any $n$-vertex graph $G$ without isolated vertices.