  If $G$ and $H$ are two cubic graphs, then an $H$-coloring of $G$ is a proper
edge-coloring $f$ with edges of $H$, such that for each vertex $x$ of $G$,
there is a vertex $y$ of $H$ with $f(\partial_G(x))=\partial_H(y)$. If $G$
admits an $H$-coloring, then we will write $H\prec G$. The Petersen coloring
conjecture of Jaeger ($P_{10}$-conjecture) states that for any bridgeless cubic
graph $G$, one has: $P_{10}\prec G$. The Sylvester coloring conjecture
($S_{10}$-conjecture) states that for any cubic graph $G$, $S_{10}\prec G$. In
this paper, we introduce two new conjectures that are related to these
conjectures. The first of them states that any cubic graph with a perfect
matching admits an $S_{12}$-coloring. The second one states that any cubic
graph $G$ whose edge-set can be covered with four perfect matchings, admits a
$P_{12}$-coloring. We call these new conjectures $S_{12}$-conjecture and
$P_{12}$-conjecture, respectively. Our first results justify the choice of
graphs in $S_{12}$-conjecture and $P_{12}$-conjecture. Next, we characterize
the edges of $P_{12}$ that may be fictive in a $P_{12}$-coloring of a cubic
graph $G$. Finally, we relate the new conjectures to the already known
conjectures by proving that $S_{12}$-conjecture implies $S_{10}$-conjecture,
and $P_{12}$-conjecture and $(5,2)$-Cycle cover conjecture together imply
$P_{10}$-conjecture. Our main tool for proving the latter statement is a new
reformulation of $(5,2)$-Cycle cover conjecture, which states that the edge-set
of any claw-free bridgeless cubic graph can be covered with four perfect
matchings.
