graph $G = (V,E)$, a map $c\colon E \to {\mathbold{N}}$ is called a *proper edge coloring* (or simply a coloring) of $G$ if for every two coincident edges $e$ and $e'$ of $G$, we have $c(e)\neq c(e')$. The colors in the image domain $c(E)$ of $c$ are called the colors *used* by $G$, and we usually write $c(G)$ for this set. For an edge $\{u,v\}\in E$, we usually write $c(u,v)$ instead $c(\{u,v\})$. Slightly abusing this notation, if $A$ is a set of vertices, then we also write $c(u,A)$ for the set $c(E(u,A))$.

### Cycles and paths

A *path* is a non-empty graph $P=(V,E)$ of the form $$V = \{p_1,p_2,\dotsc,p_k\} \quad \text{and}\quad E = \{\{p_1,p_2\},\{p_2,p_3\},\dotsc,\{p_{k-1},p_k\}\},$$ which we usually denote by the sequence $(p_1,p_2,\dotsc,p_k)$. Then $p_1$ and $p_k$ are the *start* and *end* vertices of $P$, respectively. The number of edges in $E$ is called the *length* of $P$. We call $p_i$ a *$k$-successor* of $p_j$ if $i>j$ and there are at most $k-1$ vertices between $p_i$ and $p_j$ on $P$. In other words, $p_i$ is a $k$-successor of $p_j$ if $0< i-j\leq k$. Equivalently, $p_j$ is a *$k$-predecessor* of $p_i$.

If $P = (p_1,p_2,\dotsc,p_k)$ is a path, then the graph $C=P 