S12 and P12-colorings of cubic graphs

Anush Hakobyan, Vahan Mkrtchyan


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.


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

Full Text:


DOI: https://doi.org/10.26493/1855-3974.1758.410

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications