Maximum odd induced subgraph of a graph concerning its chromatic number

Abstract

Let $f_o(G)$ be the maximum order of an odd induced subgraph of $G$. In 1992, Scott proposed a conjecture that $f_o(G)\ge \frac{n}{2\chi (G)}$ for a graph $G$ of order $n$ without isolated vertices, where $\chi (G)$ is the chromatic number of $G$. In this paper, we show that the conjecture is not true for bipartite graphs, but is true for all line graphs. In addition, we also disprove a conjecture of Berman, Wang and Wargo in 1997, which states that $f_o(G)\ge 2\lfloor \frac{n}{4}\rfloor$ for a connected graph $G$ of order $n$. Scott's conjecture is open for a graph with chromatic number at least 3.

18 pages, 6 figure