 Semicoloring by independent hyperplanes

Suppose a graph with $n$ vertices and $m>0$ edges has a vector coloring with adjacent inner products at most $-1/2$. Take $r$ independent copies of random hyperplane rounding and use the $r$ signs as a color. Each edge remains monochromatic with probability at most $3^{-r}$, so the expected number $B$ of monochromatic edges is at most $m{3}^{-r}$ by linearity of expectation.

Choose $r=\max \{0,\lceil {\log }_3(4m/n)\rceil \}$. Then Markov inequality gives $\mathbb{P}(B>n/2)\le 1/2$. On success, delete one endpoint of every monochromatic edge. This random alteration method leaves at least $n/2$ vertices properly colored withThe removed vertices can retain their original colors, as the semicoloring only requires the retained induced subgraph to be proper. A failed draw can be detected and repeated, with at most two trials on average. The case $m=0$ needs just one color. This is the elementary independent-hyperplane construction in Karger, Motwani and Sudan's paper on approximate graph coloring.