A counterexample to the $S_{10}$- and the $S_{12}$-Conjecture

Abstract

For two graphs $G$ and $H$, a mapping $f:E(G)\to E(H)$ is an $H$-coloring of $G$, if it is a proper edge-coloring and for every $v\in V(G)$ there exists a vertex $u\in V(H)$ with $f({\partial }_G(v))={\partial }_H(u)$. Motivated by the Petersen Coloring Conjecture, Mkrtchyan [A remark on the Petersen coloring conjecture of Jaeger, \emph{Australas. J. Combin.}, 56 (2013), 145-151] and Mkrtchyan together with Hakobyan [$S_{12}$ and $P_{12}$-colorings of cubic graphs, \emph{Ars Math. Contemp.}, 17 (2019), 431-445] made the following two conjectures. (I) Every cubic graph has an $S_{10}$-coloring, where $S_{10}$ is a graph on 10 vertices sometimes also referred to as the Sylvester graph. (II) Every cubic graph with a perfect matching has an $S_{12}$-coloring, where $S_{12}$ is the graph obtained from $S_{10}$ by replacing the central vertex with a triangle. In this note we present a (rather small) counterexample to both conjectures.

6 pages, submitted for publication