  Let $H$ and $G$ be graphs. An $H$-colouring of $G$ is a proper edge-colouring
$f:E(G)\rightarrow E(H)$ such that for any vertex $u\in V(G)$ there exists a
vertex $v\in V(H)$ with $f\left (\partial_Gu\right )=\partial_Hv$, where
$\partial_Gu$ and $\partial_Hv$ respectively denote the sets of edges in $G$
and $H$ incident to the vertices $u$ and $v$. If $G$ admits an $H$-colouring we
say that $H$ colours $G$. The question whether there exists a graph $H$ that
colours every bridgeless cubic graph is addressed directly by the Petersen
Colouring Conjecture, which states that the Petersen graph colours every
bridgeless cubic graph. In 2012, Mkrtchyan showed that if this conjecture is
true, the Petersen graph is the unique connected bridgeless cubic graph $H$
which can colour all bridgeless cubic graphs. In this paper we extend this and
show that if we were to remove all degree conditions on $H$, every bridgeless
cubic graph $G$ can be coloured substantially only by a unique other graph: the
subcubic multigraph $S_{4}$ on four vertices. A few similar results are
provided also under weaker assumptions on the graph $G$. In the second part of
the paper, we also consider $H$-colourings of regular graphs having degree
strictly greater than $3$ and show that: (i) for any $r>3$, there does not
exist a connected graph $H$ (possibly containing parallel edges) that colours
every $r$-regular multigraph, and (ii) for every $r>1$, there does not exist a
connected graph $H$ (possibly containing parallel edges) that colours every
$2r$-regular simple graph.
