vertex cover , 3/2-approximation algorithm Consider the vertex cover problem.
How can I give a 3/2-approximation algorithm for the vertex cover problem , when the input graph is planar?
We can use the facts  that polynomial-time LP solvers return extreme points , and that there is a polynomial-time algorithm to 4-colour any planar graph ( i.e. , the algorithm assigns each vertex one of four colours such that for any edge (i,j) that belongs to E , vertices i and j have been asigned different colours.) However,I don't know in which way this might be helpful.
 A: In general, the idea of LP-based approximation algorithms is that you want to start with the solution to the vertex cover linear program (which assigns an element of $\{0,\frac12,1\}$ to every vertex) and turn it into an integer solution without changing the objective value too much.
Since the optimal value of the linear relaxation is at most the optimal value of the actual vertex cover problem, if you don't deviate from that optimal value by more than a factor of $\frac32$, you have a $\frac32$ approximation algorithm.
In this case, the LP solution assigns some vertices value either $0$ or $1$ (which we don't need to change) and other vertices value $\frac12$ (which we do need to change). In the worst case, we have $n$ vertices with value $\frac12$, for objective value $\frac 12 n$. For a $\frac32$ approximation, we are allowed to go up to objective value $\frac34 n$: giving at most $\frac34$ of the fractional vertices value $1$, and the rest value $0$.
Solution:

 To do this, $4$-color the graph (as indicated by the hint) and choose the color (say, red) with the most fractional vertices. Give all fractional vertices that are red value $0$, and give all other fractional vertices value $1$. No edge can have two red vertices incident to it, so all edges are still covered. At most $\frac34$ of the fractional vertices were not red, so we went from half-using each vertex to using $\frac34$ of them, multiplying the objective value by at most $\frac32$.

(Essentially the same idea works for the variant where the vertices are weighted, if that's a concern.)
