I've got this exercise to solve for a homework and I've got no idea, any help would be appreciated, thanks in advance.
(a) Every graph $G$ has a $\chi(G)$-coloring in which at least one of its coloring classes is a maximal stable set.
(b) Let $G = (V, E)$ be a graph and $x, y \in V$ such that $xy \notin E$. Prove that $\chi(G) = \min \{χ(G + xy), \chi(G|xy)\}$, where $G|xy$ denotes the contraction of the pair $(x, y)$ in $G$.
On
I can help with part (b) a bit. It becomes quite obvious if you consider $2$ cases: vertices $x$ and $y$ are same color or have different colors for some coloring with $\chi(G)$ -- number of colors used.
Let us consider some coloring with $\chi(G)$ -- number of colors used.
If $x$ and $y$ have different colors, you can keep current coloring after adding an edge between them, thus number of colors cannot increase. Number of colors cannot decrease as well, otherwise you would be able to remove $xy$ and get smaller $\chi$ for original graph, thus $\chi(G + xy) = \chi(G)$. Now consider gluing this points together -- you can either find some different coloring that retains the number of colors, or number of colors should increase $\chi(G|xy) \geq \chi(G)$. Note that number of colors can never decrease, otherwise you would be able to "unglue" $xy$ and get the previous graph with smaller $\chi$ that should be not possible.
If $x$ and $y$ have the same color, contracting them changes nothing, thus $\chi(G|xy) = \chi(G)$. On the other hand, adding an edge $xy$ forces us to recolor graph and we get the same or greater number of colors $\chi(G+xy) \geq \chi(G)$ (proof by contradiction as I did previously).
As a result we get $\min\{\chi(G+xy), \chi(G|xy)\} = \chi(G)$
For part (a), consider any coloring of $G$ with $\chi(G)$ colors, and fix one color, say red. If the red color class is not a maximal stable set, then find a vertex that we can add to it and still have a stable set. Recolor this vertex red. Keep doing this until the red color class is maximal, i.e., until we cannot add any more red vertices.
As for part (b), it's pretty obvious that $\chi(G)\le\chi(G+xy)$. Also, if we consider a coloring of $G|xy$ with $\chi(G|xy)$ colors, then we can color the graph $G$ by coloring $x$ and $y$ the same color as the contracted $(x,y)$, and coloring everything else the same. So $\chi(G)\le\chi(G|xy)$.
Now if $\chi(G)<\chi(G+xy)$, then we know that every coloring of $G$ using $\chi(G)$ colors must have $x$ and $y$ colored the same. Otherwise, we could use the same coloring for $G+xy$.
So pick a coloring of $G$ with $\chi(G)$ colors. Then for the graph $G|xy$, just consider the exact same coloring, where every $v\ne x,y$ is colored the same as it was in $G$, and the contracted vertex $(x,y)$ is colored the same color as $x$ and $y$ were (since $x$ and $y$ have the same color).
This means that if $\chi(G)<\chi(G+xy)$, then $\chi(G)=\chi(G|xy)$. The result follows immediately from this.
As a note, part (a) isn't true if we require that at least one of the color classes be a maximum stable set (as I'd initially misread the problem statement). Consider a graph with eight vertices as follows: Draw a $K_4$ as a square with a cross, then draw a triangle on each outer edge of the square.
Clearly the chromatic number is at least four, since we have a $K_4$ in the middle. It's pretty easy to see that you can color this graph with four vertices. So $\chi(G)=4$. It's also easy to see that the only maximal independent (stable) set is the set made of the four outer vertices.
We would like to be able to find a coloring so that those four vertices are all the same color. But if they were the same color, then we'd need four more colors to color the inner $K_4$, giving us a total of five colors.