= 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 $m3^{-r}$ by <linearity of expectation>.
Choose $r=\max\{0,\lceil\log_3(4m/n)\rceil\}$. Then <Markov inequality> gives $\mathbb P(B>n/2)\leq1/2$. On success, delete one endpoint of every monochromatic <edge>. This <random alteration method> leaves at least $n/2$ <vertices> properly colored with
$$
k=2^r=O\left(\max\{1,(m/n)^{\log_3 2}\}\right)=O(n^{\log_3 2}).
$$
The 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 https://arxiv.org/abs/cs/9812008[Karger, Motwani and Sudan's paper on approximate graph coloring].
Back to article page
