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.

  • $\begingroup$ Is $\overline G$ the complement of $G$? Is $|G|$ the number of vertices? And what is a feedback vertex set of $G$? $\endgroup$ – bof Feb 8 at 11:16
  • 1
    $\begingroup$ @bof This is standard notation, yet I edited with the definitions. $\endgroup$ – joro Feb 8 at 11:45
  • $\begingroup$ It might be easier to think of $|G|-MFVS(\bar G)$ as the size of the largest induced subforest of $\bar G$. $\endgroup$ – Martin Rubey Feb 8 at 14:10
  • 1
    $\begingroup$ 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. $\endgroup$ – Martin Rubey Feb 8 at 14:40
  • 1
    $\begingroup$ @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? $\endgroup$ – joro Feb 8 at 15:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.