3/2 - Approximation probabilistic algorithm for MAX-3-COLOR I have a textbook question here regarding Max-3-Coloring and need some assistance with it. I have searched for any type of information regarding it but haven't found anything substantial. Here is the question:


  In MAX-3-COLOR you are given a graph $G=(V,E)$ and your goal is to
  find a coloring of the vertices with only 3 colors $c: V \rightarrow
 [3]$ that maximizes the quality function $q(c)$ - The number of edges
  whose endpoint vertices are colored with different colors: 
  
  $\sum_{(i,j)\in E} (1_{c(i) \neq c(j)})$
  
  Give a probabilistic $3/2$-approximation algorithm. (i.e $q(c)\geq 2/3 \cdot OPT$ 
  with probability at least $1-\frac{1}{e^{k}}$ for any $k \in \mathbb{N}$


OK so up until now the textbook only talks about one probabilistic algorithm which fits the requirements - MAX-3-SAT. The textbook gives a probabilistic $8/7$ - approximation algorithm for it (for every literal, toss a fair coin and decide whether to set it to $True$ or $False$).

I also found several other sources which prove that the 3-COLOR is NP-Complete by reducing it to the 3-SAT problem. Thus I am pretty confident that MAX-3-SAT is the way to go.

According to this thread: 3 Colorability reduction to SAT I thought about doing the same thing:


  For every $x \in V$ create three literals: $x_1, x_2, x_3 \in \{{True,
 False}\}$ where each literal denotes if said vertex $x$ is colored
  with color $i$. 
  
  Then for every edge $e =(x,y)\in E$ create the following
  3-CNF formula $\varphi$:
  
  $ \varphi_e = (\urcorner x_1 \vee \urcorner y_1 \vee \urcorner y_1)
 \wedge (\urcorner x_2 \vee \urcorner y_2 \vee \urcorner y_2) \wedge
 (\urcorner x_3 \vee \urcorner y_3 \vee \urcorner y_3) \wedge (x_1 \vee
 x_2 \vee x_3)$
  
  And the final formula $\phi$ is:
  
  $\phi = \bigwedge_{e \in E} \varphi_e$


Every 3-CNF formula for an edge makes sure that the two endpoints are not of the same color and that one of them is either color 1, 2 or 3.

The thing is I don't see how this would help me. This gives me a MAX-3-SAT problem since I have a 3-CNF formula for every edge and one big 3-CNF formula for the whole graph. So technically I could use the same algorithm that was given in the textbook before

But wouldn't using the same probabilistic probabilistic $8/7$ - approximation algorithm for the MAX-3-SAT give the exact same approximation? whereas I wish to achieve a $3/2$- approximation

Thanks to anyone who helps!
If you simply uniformly at random (i.i.d) color each of the vertices of $V$ by each of the three possible colors, then for every edge $e\in E$, it's endpoint will be colored by different colors w.p. $\frac{2}{3}$, hence the expected quality of the random coloring is exactly $\frac{2|E|}{3}$. We know that the optimal quality is at most $q^*\leq |E|$, hence this is a $\frac{3}{2}$ approximation.