  In the Euclidean $k$-means problems we are given as input a set of $n$ points
in $\mathbb{R}^d$ and the goal is to find a set of $k$ points $C\subseteq
\mathbb{R}^d$, so as to minimize the sum of the squared Euclidean distances
from each point in $P$ to its closest center in $C$. In this paper, we formally
explore connections between the $k$-coloring problem on graphs and the
Euclidean $k$-means problem. Our results are as follows:
  $\bullet$ For all $k\ge 3$, we provide a simple reduction from the
$k$-coloring problem on regular graphs to the Euclidean $k$-means problem.
Moreover, our technique extends to enable a reduction from a structured max-cut
problem (which may be considered as a partial 2-coloring problem) to the
Euclidean $2$-means problem. Thus, we have a simple and alternate proof of the
NP-hardness of Euclidean 2-means problem.
  $\bullet$ In the other direction, we mimic the $O(1.7297^n)$ time algorithm
of Williams [TCS'05] for the max-cut of problem on $n$ vertices to obtain an
algorithm for the Euclidean 2-means problem with the same runtime, improving on
the naive exhaustive search running in $2^n\cdot \text{poly}(n,d)$ time.
  $\bullet$ We prove similar results and connections as above for the Euclidean
$k$-min-sum problem.
