S_12 and P_12-colorings of cubic graphs

Anush Hakobyan ; Vahan Mkrtchyan

Ars Mathematica Contemporanea, Tome 17 (2019) no. 2, pp. 431-445.

Résumé

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.

Détail

DOI : 10.26493/1855-3974.1758.410

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