What is the LP gap of vertex cover in planar graphs? 


The LP I refer to is min $\sum\_{e \in E } c\_e x\_e \ \ $ subject to $ \ \ x\_v + x\_u \geq 1 \ \ \ \forall uv \in E $  

$ c\_e \geq 0 $ are costs of the vertices 


Also is there an LP with a smaller gap?


(I posted this in mathstackexchange where it was labelled offtopic if it is offtopic here please tell me where I should post this.)



What is the LP gap of vertex cover in planar graphs?
The vertex cover LP gap is $\frac32$ for planar graphs. The $\frac32$ follows by looking at an extreme point optimal LP solution with values in $\{0, \frac12, 1\}$. Let $V\_{i}$ be the set of vertices with LP value $i$ for all $i \in \{0, \frac12, 1\}$. Now we create an integral vertex cover. In this vertex cover take all the $V\_1 $vertices. Now, look at any $4$ coloring of the graph. This coloring will partition $V\_{\frac12}$ into 4 part. Now to our vertex cover, we add all the vertices in $V\_{\frac12}$ except the part with a maximum cost.
It is easy to see that what we get is a vertex cover of cost at most $\frac32$ times the LP value. 


$K\_4$ gives a tight lower bound of $\frac32$.


