  Computing the smallest number $q$ such that the vertices of a given graph can
be properly $q$-colored is one of the oldest and most fundamental problems in
combinatorial optimization. The $q$-Coloring problem has been studied
intensively using the framework of parameterized algorithmics, resulting in a
very good understanding of the best-possible algorithms for several
parameterizations based on the structure of the graph. While there is an
abundance of work for parameterizations based on decompositions of the graph by
vertex separators, almost nothing is known about parameterizations based on
edge separators. We fill this gap by studying $q$-Coloring parameterized by
cutwidth, and parameterized by pathwidth in bounded-degree graphs. Our research
uncovers interesting new ways to exploit small edge separators.
  We present two algorithms for $q$-Coloring parameterized by cutwidth $cutw$:
a deterministic one that runs in time $O^*(2^{\omega \cdot cutw})$, where
$\omega$ is the matrix multiplication constant, and a randomized one with
runtime $O^*(2^{cutw})$. In sharp contrast to earlier work, the running time is
independent of $q$. The dependence on cutwidth is optimal: we prove that even
3-Coloring cannot be solved in $O^*((2-\varepsilon)^{cutw})$ time assuming the
Strong Exponential Time Hypothesis (SETH). Our algorithms rely on a new rank
bound for a matrix that describes compatible colorings. Combined with a simple
communication protocol for evaluating a product of two polynomials, this also
yields an $O^*((\lfloor d/2\rfloor+1)^{pw})$ time randomized algorithm for
$q$-Coloring on graphs of pathwidth $pw$ and maximum degree $d$. Such a runtime
was first obtained by Bj\"orklund, but only for graphs with few proper
colorings. We also prove that this result is optimal in the sense that no
$O^*((\lfloor d/2\rfloor+1-\varepsilon)^{pw})$-time algorithm exists assuming
SETH.
