Following to my previous question on the same topic, I would like to have some opinions whether the present refinement have some chances to work or is doomed to fail.

Given the positive integers $n$ and $m$, consider the set of graphs $\mathcal{G} = \{G=(V,E): |V|=n \land |E|=m\}$.

For which values of $n$ and $m$ does the following requirement hold:

$\forall G \in \mathcal{G}$ there exists at least one $k$-partite subgraph of $G$ with $2 \le k \le n$ and with parts $V_1, \ldots ,V_k$ such that:

$$\prod_{j=1}^k (1+|V_j|)-1 \gt \frac{4n}{3}?$$

In particular I am interested in the case $n=39$ and $m=113$. With respect to the previous question, I have lowered $n$ but increased the minimum of the expression to $4n/3$. I am not sure how to adapt the counterexamples there to this generalization of the problem.