  In this work we start the investigation of tight complexity bounds for
connectivity problems parameterized by cutwidth assuming the Strong
Exponential-Time Hypothesis (SETH). Van Geffen et al. posed this question for
odd cycle transversal and feedback vertex set. We answer it for these two and
four further problems, namely connected vertex cover, connected domintaing set,
steiner tree, and connected odd cycle transversal. For the latter two problems
it sufficed to prove lower bounds that match the running time inherited from
parameterization by treewidth; for the others we provide faster algorithms than
relative to treewidth and prove matching lower bounds. For upper bounds we
first extend the idea of Groenland et al.~[STACS~2022] to solve what we call
coloring-like problem. Such problems are defined by a symmetric matrix $M$ over
$\mathbb{F}_2$ indexed by a set of colors. The goal is to count the number
(modulo some prime $p$) of colorings of a graph such that $M$ has a $1$-entry
if indexed by the colors of the end-points of any edge. We show that this
problem can be solved faster if $M$ has small rank over $\mathbb{F}_p$. We
apply this result to get our upper bounds for connected vertex cover and
connected dominating set. The upper bounds for odd cycle transversal and
feedback vertex set use a subdivision trick to get below the bounds that matrix
rank would yield.
