  We study a new variant of \emph{connected coloring} of graphs based on the
concept of \emph{strong} edge coloring (every color class forms an
\emph{induced} matching). In particular, an edge-colored path is \emph{strongly
proper} if its color sequence does not contain identical terms within a
distance of at most two. A \emph{strong proper connected} coloring of $G$ is
the one in which every pair of vertices is joined by at least one strongly
proper path. Let spc($G$) denote the least number of colors needed for such
coloring of a graph $G$. We prove that the upper bound spc($G$)$\leq${5} holds
for any $2$-connected graph $G$. On the other hand, we demonstrate that there
are $2$-connected graphs with arbitrarily large girth satisfying
spc($G$)$\geq${4}. Additionally, we prove that graphs whose cycle lengths are
divisible by $3$ satisfy spc($G$)$\leq{3}$. We also consider briefly other
connected colorings defined by various restrictions on color sequences of
connecting paths. For instance, in a \emph{nonrepetitive connected coloring} of
$G$, every pair of vertices should be joined by a path whose color sequence is
\emph{nonrepetitive}, that is, it does not contain two adjacent identical
blocks. We demonstrate that $2$-connected graphs are $15$-colorable while
$4$-connected graphs are $6$-colorable, in the connected nonrepetitive sense. A
similar conclusion with a finite upper bound on the number of colors holds for
a much wider variety of connected colorings corresponding to fairly general
properties of sequences. We end the paper with some open problems of concrete
and general nature.
