Here is a construction with $\Omega(1/k)$ fraction: consider $x_1x_2+x_3x_4+\dots \mod p$. In which $p$ is a prime larger than $k$. If two vertices are adjacent, their difference is $(b-c)(a-d)$, which is not divided by $p$. Thus one can take the largest residue class.
Peter Wu
- 301
- 1
- 9