Ssub{12} and Psub{12}-colorings of cubic graphs

english

2019

volume 17, issue 2

?$S_{10}$?-conjecture   cubic graph   Petersen coloring conjecture   Petersen graph

Univerza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije
(Obvezni izvod spletne publikacije)

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(\partial_G(x)) = \partial_H(y)$?. If ?$G$? admits an ?$H$?-coloring, then we will write ?$H\prec G$?. The Petersen coloring conjecture of Jaeger (?$P_{10}$?-conjecture) states that for any bridgeless cubic graph ?$G$?, one has: ?$P_{10} \prec G$?. The ?$S_{10}$?-conjecture states that for any cubic graph ?$G$?, ?$S_{10} \prec 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.

29.05.2020