Lower bound on the size of maximum interval induced subgraphs of an $n$-vertex graph $G$ Let $H$ be a maximum induced interval subgraph of a graph $G=(V,E)$.  If $n=|V|$， then what is the smallest number of $V(H)$?

The number is at most $3n/4$： consider a set of disjoint $4$-holes.

Can it be smaller?
We can do $2\sqrt{n}-1$; consider the complete $\sqrt{n}$-partite graph, as long as there are two parties both with more than one node inside there is an induced $C_4$, so it cannot be inteval.  Therefore we have to remove at least $(\sqrt{n}-1)^2 = n - 2\sqrt{n} + 1$ nodes to destroy all the induced $C_4$.