*S*_{12} and *P*_{12}-colorings of cubic graphs

#### Abstract

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 (*P*_{10}-conjecture) states that for any bridgeless cubic graph*G*, one has:*P*_{10}≺*G*. The*S*_{10}-conjecture states that for any cubic graph*G*,*S*_{10}≺*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*S*_{12}-coloring. The second one states that any cubic graph*G*whose edge-set can be covered with four perfect matchings, admits a*P*_{12}-coloring. We call these new conjectures*S*_{12}-conjecture and*P*_{12}-conjecture, respectively. Our first results justify the choice of graphs in*S*_{12}-conjecture and*P*_{12}-conjecture. Next, we characterize the edges of*P*_{12}that may be fictive in a*P*_{12}-coloring of a cubic graph*G*. Finally, we relate the new conjectures to the already known conjectures by proving that*S*_{12}-conjecture implies*S*_{10}-conjecture, and*P*_{12}-conjecture and (5, 2)-Cycle cover conjecture together imply*P*_{10}-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.#### Keywords

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

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