# Lower bound for the chromatic number in terms of minimum feedback vertex set

Let $$MFVS(G)$$ denote the size of minimum feedback vertex set of $$G$$.

We believe we proved $$\chi(G) \ge (|G| - MFVS(\overline{G}))/2$$ and this bound is sharp.

Is this known or trivial result?

This is standard notation and to address comments $$|G|$$ is the number of vertices of $$G$$, $$\overline{G}$$ is the complement of $$G$$ and feedback vertex set $$S$$ is subset of $$V(G)$$ such that deleting $$S$$ from $$G$$ leaves acyclic graph.

• Is $\overline G$ the complement of $G$? Is $|G|$ the number of vertices? And what is a feedback vertex set of $G$? – bof Feb 8 at 11:16
• @bof This is standard notation, yet I edited with the definitions. – joro Feb 8 at 11:45
• It might be easier to think of $|G|-MFVS(\bar G)$ as the size of the largest induced subforest of $\bar G$. – Martin Rubey Feb 8 at 14:10
• Here is an easy proof: consider any proper colouring of $G$, with colour classes $n_1,\dots,n_{\chi(G)}$. Then the complement of the complete multipartite graph is a collection of cliques, from each of which we can choose at most two vertices to have an induced subforest. Since this collection of cliques is a subgraph of $\bar G$, the largest induced subforest of the latter can only be smaller. – Martin Rubey Feb 8 at 14:40
• @MartinRubey Thanks :) My proof is different. Is this known? And can your solution compute the RHS in time n^(2*chi(G)) if chi(G) is given? – joro Feb 8 at 15:43