Chromatic number of random spanning subgraph
For $k=5$ (or any other fixed $k$), since we can choose $c$ to be anything we like, we just need some bound on the probability independent of the number of vertices.
In fact, we can show that the probability is at most $\frac12$, once we prove the following lemma:
Let $H_1$ and $H_2$ be graphs on the same vertex set, and let $H_1 \cup H_2$ be the graph obtained by taking all edges present in either $H_1$ or $H_2$. Then $\chi(H_1 \cup H_2) \le \chi(H_1) \cdot \chi(H_2)$.
Proof: Given an $r_i$-coloring $f_i$ of $H_i$ for $i \in \{1,2\}$, we can construct an $r_1r_2$-coloring of $H_1 \cup H_2$ by giving $v$ the color $(f_1(v), f_2(v))$. If $v$ and $w$ are adjacent in $H_1 \cup H_2$, either they're adjacent in $H_1$ (and $f_1(v) \ne f_1(w)$) or they're adjacent in $H_2$ (and $f_2(v) \ne f_2(w)$), so in either case we have $(f_1(v), f_2(v)) \ne (f_1(w), f_2(w))$.
Given a spanning subgraph $G'$ of $G$, if we let $G''$ be the graph formed by taking all edges of $G$ not in $G'$, then $4 < \chi(G) \le \chi(G') \cdot \chi(G'')$, so either $\chi(G') > 2$ or $\chi(G'') > 2$. So we've divided all possible graphs into pairs where at least one graph has chromatic number more than $2$, which means that $\Pr[\chi(G') \le 2]$ is at most $\frac12$.
To use this to get the general bound we want, it's enough to partition the edge set $E$ into $\Omega(k^2)$ disjoint parts $E_1, E_2, \dots, E_t$, such that $\chi(G_{E_i}) \ge 5$ for all $i$. Then for a randomly chosen $E' \subseteq E$, $\chi(G_{E'}) \le 2$ only if $\chi(G_{E' \cap E_i}) \le 2$ for all $i$. These are $t$ independent events with probability at most $\frac12$ by the argument above, so $\Pr[\chi(G_{E'}) \le 2] \le 2^{-t}$.
To find $E_1, \dots, E_t$, fix a $k$-coloring $f$ of $G$, and consider sets $V_{abcde} = f^{-1}(\{a,b,c,d,e\})$ for some colors $a, b, c, d, e$. It's not hard to see that if we let $E_{abcde}$ be the set of all edges between pairs of vertices in $V_{abcde}$, then $\chi(G_{E_{abcde}}) = 5$; we have $E_{abcde} \cap E_{a'b'c'd'e'} = \varnothing$ if at most one color is shared between $\{a,b,c,d,e\}$ and $\{a',b',c',d',e'\}$.
So it remains to choose $\Omega(k^2)$ subsets of $\{1,2,\dots,k\}$ of size $5$ among which no two share more than one element, which can be done probabilistically using a first moment calculation.