<i>S</i><sub>12</sub> and <i>P</i><sub>12</sub>-colorings of cubic graphs


  • Anush Hakobyan
  • Vahan Mkrtchyan




Cubic graph, Petersen graph, Petersen coloring conjecture, S_10-conjecture


If G and H are two cubic graphs, then an H-coloring of G is a proper edge-coloring f with the edges of H, such that for each vertex x of G, there is a vertex y of H with f(G(x)) = H(y). If G admits an H-coloring, then we will write H ≺ G. The Petersen coloring conjecture of Jaeger (P10-conjecture) states that for any bridgeless cubic graph G, one has: P10 ≺ G. The S10-conjecture states that for any cubic graph G, S10 ≺ 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 S12-coloring. The second one states that any cubic graph G whose edge-set can be covered with four perfect matchings, admits a P12-coloring. We call these new conjectures S12-conjecture and P12-conjecture, respectively. Our first results justify the choice of graphs in S12-conjecture and P12-conjecture. Next, we characterize the edges of P12 that may be fictive in a P12-coloring of a cubic graph G. Finally, we relate the new conjectures to the already known conjectures by proving that S12-conjecture implies S10-conjecture, and P12-conjecture and (5, 2)-Cycle cover conjecture together imply P10-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.