This way each vector ui is assigned a spoke, i.e. a color. It may happen that this coloring is not legal, because two adjacent vectors are assigned the same spoke. However this happens with low probability.
A detailed analysis shows that two unit vectors with product bounded by - 1 /(k - 1) are assigned the same spoke among t spokes with probability t-k/(k-2). The maximum of k-k/(k-2) is 0.0686 for k = 5 .365.
From these results techniques have been developed which assign a semicoloring to the graph, i.e. a fixed fraction of edges may receive illegal colors. So some nodes are colored with additional colors and so on. In this way random polynomial algorithms can be designed with a bounded number of colors.
