Can someone please provide a direction with the following:
If you take a graph $G=(V,E)$ with chromatic number $k$ and then go over its edges removing each edge with probability $\frac{1}{2}$. What is the probability that the resulting graph will have chromatic number $k$? what is the probability that the resulting graph will have chromatic number $k-1$?
Some thoughts of mine about this is that the chromatic number will decrease if and only if there exists a $k$-coloring of $G$ which creates independent vertices sets $V_1$,...,$V_k$ (the union of which is $V$) and there exists $i\ne{j}$ such that the edges removal removes all edges between $V_i$ and $V_j$. But it seems too complicated to calculate the probability of such event.
I'm still not sure what an answer to this question looks like, since the probability depends a lot on the structure of $G$, but here are some deeper observations.
We could ask about the behavior of a typical graph with chromatic number $k$ (e.g., the behavior of the Erdős–Rényi graph $\mathcal G_{n,1/2}$, conditioned on $\chi(\mathcal G_{n,1/2}) = k$). For $k$ not too large, this is approximately the same as choosing a uniformly random $k$-partite graph, with the caveat that actually the size of each part will not be $n/k$, but maybe $n/k \pm O(\sqrt{n})$ or something like that (I don't think that this consideration changes the behavior significantly).
If $G$ is a uniformly random $k$-partite graph, then removing each edge of $G$ with probability $\frac12$ leaves a $k$-partite graph where each edge is present with probability $\frac14$. Then the expected number of $k$-cliques in the resulting graph is $$\left(\frac{n}{k}\right)^k \cdot 2^{-\binom k2} = \left(\frac{n}{k\, 2^{(k-1)/2}}\right)^k$$ so there is some threshold for $k$, that is asymptotically $O(\log n)$, at which we are nearly guaranteed to see one of these cliques. So for these graphs, the chromatic number almost never changes.
But in another sense, these graphs are very atypical graphs with chromatic number $k$: they are far too dense for this chromatic number to arise naturally. So instead, we could look at $\mathcal G_{n,p}$ for a range of $p$ and just deal with the chromatic number we end up getting.
In that case, randomly removing edges gives us a $\mathcal G_{n,p/2}$ coupled with our original random graph, and this almost certainly has a different chromatic number. For $p \gg \frac1n$, we have $\mathcal G_{n,p} \sim \frac{np}{2\log np}$, with concentration on an interval of length $O(\sqrt n)$ or something like that, and cutting $p$ in $2$ guarantees that these intervals don't overlap.
For $p = \frac dn$, we have two-point concentration of the chromatic number on a value of $k$ satisfying $k \sim \frac{d}{\log d}$. Somewhere between $k=3$ and $k=5$, these values can overlap, but for larger $k$ (and larger $d$), we once again are guaranteed with high probability (in $n$) that the thinned-out graph has smaller chromatic number.
However, I think we can use this fact about sparse random graphs to create a sparse graph $G$ with chromatic number $k$ for any constant $k$ that will keep its chromatic number when thinned out. Starting with a $\mathcal G_{n,d/n}$ that has chromatic number $k$ with high probability, replace each vertex by $kr$ vertices (for a value of $r$ I'll choose later) and each edge by a copy of $K_{kr,kr}$, only inflating the vertex count by $kr$ and the edge count by $(kr)^2$.
Each group of vertices in this blow-up has a majority color present on at least $r$ of the vertices. After the thinning-out happens, I'll say that an edge survives if, in the thinned out $K_{kr,kr}$, there is no group of $r$ vertices on one side and $r$ vertices on the other with no edges between them. An edge survives with probability $$ s \ge 1 - \binom{kr}{r}^2 2^{-r^2} \ge 1 - \left(\frac{(kr)^2}{2^r}\right)^r.$$ For $r = C \log_2 k$ with $C \ge 3$ or so, this survival probability is better than $1 - 2^{-C}$ (we might have to take larger $C$ when $k$ is small). But then, the graph we get by going back to the $n$-vertex graph and keeping edges for which the corresponding $K_{kr,kr}$ survives is a $\mathcal G_{n,sd/n}$ with $ps$ very close to $p$. For each $k$, there is some $C$ we can take such that $\chi(\mathcal G_{n,sd/n}) = \chi(\mathcal G_{n,d/n})$ with high probability, and therefore the blow-up keeps its chromatic number after being thinned out.