The vertex coloring of an undirected graph $G = (V,E)$ is to assign as few colors as possible to each node such that adjacent node has different colors. I know that this problem can be represented as a linear programming problem:
\begin{align}
\text{min} & \sum_{1 \leq i \leq H} w_i \\
\text{s.t } & \sum_{i=1}^H x_{v,i} = 1 && \forall v \in V \\
& x_{u,i} + x_{v,i} \leq w_i && \forall (u,v) \in E, \ i = 1,\dots,H\\
& x_{v,i}, w_i \in \{0,1\} && \forall v \in V, \ i = 1,\dots,H. \\
\end{align}
How can i show that this problem can not have an $\alpha$-approximation algorithm with $\alpha < 4/3$ unless P=NP ? One of my idea is to related this with the vertex cover problem whereas for the vertex cover, the $\alpha$ can not be smaller than 1.3606 unless P = NP but i do not know how to proceed. The wiki https://en.wikipedia.org/wiki/Graph_coloring#Bounds_on_the_chromatic_index mentions something about edge coloring with approximation cannot be better than $4/3$ but it does not say how. Any help is appreciated.
Best Answer
I think that if you gave me an approximation algorithm with $\alpha < 4/3$ then I could solve the NP-complete problem $3$-colourability.
I would run the approximation algorithm and if it reports a value less than $4$, then I claim the original graph is $3$-colourable. If it reports a value of $4$ or more then the original graph is not $3$-colourable.