2025/09/17 by Isaak H. Wolf, Wolf, Isaak H.
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2509.14184
openalex publication_date 2025/09/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For two graphs G and H, a mapping f\colon E(G) → E(H) is an H-coloring of G, if it is a proper edge-coloring and for every v ∈ V(G) there exists a vertex u ∈ V(H) with f(∂G(v))=∂H(u). Motivated by the Petersen Coloring Conjecture, Mkrtchyan [A remark on the Petersen coloring conjecture of Jaeger, Australas. J. Combin., 56 (2013), 145-151] and Mkrtchyan together with Hakobyan [S12 and P12-colorings of cubic graphs, Ars Math. Contemp., 17 (2019), 431-445] made the following two conjectures. (I) Every cubic graph has an S10-coloring, where S10 is a graph on 10 vertices sometimes also referred to as the Sylvester graph. (II) Every cubic graph with a perfect matching has an S12-coloring, where S12 is the graph obtained from S10 by replacing the central vertex with a triangle. In this note we present a (rather small) counterexample to both conjectures.