343 KB43 KB200820252019Hakobyan, AnushMkrtchyan, Vahanletnik:17številka:2str. 431-445ISSN:1855-3966COBISSID_HOST:18957401URN:URN:NBN:SI:doc-5CVYESBIenUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporanea?$S_{10}$?-conjecture?$S_{10}$?-domnevacubic graphdomneva o petersenskem barvanjukubični grafPetersen coloring conjecturePetersen graphPetersenov grafSsub{12} and Psub{12}-colorings of cubic graphs|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Če sta ?$G$? in ?$H$? kubična grafa, potem je ?$H$?-barvanje grafa ?$G$? pravilno povezavno barvanje ?$f$? s povezavami grafa ?$H$?, takšno da za vsako vozlišče ?$x$? grafa ?$G$? obstaja vozlišče ?$y$? grafa ?$H$?, za katero je ?$f(\partial_G(x)) = \partial_H(y)$?. Če ?$G$? dopušca ?$H$?-barvanje, potem bomo pisali ?$H\prec G$?. Jaegerjeva domneva o petersenskem barvanju (?$P_{10}$?-domneva) pravi, da za poljuben brezmostni kubični graf ?$G$? velja ?$P_{10} \prec G$?. ?$S_{10}$?-domneva pravi, da za poljuben kubični graf ?$G$? velja ?$S_{10} \prec G$?. V članku vpeljeva dve novi domnevi, ki sta povezani s tema domnevama. Prva od njiju pravi, da poljuben kubični graf s popolnim prirejanjem dopušca ?$S_{12}$?-barvanje. Druga pravi, da poljuben kubični graf ?$G$?, katerega povezavno množico se da pokriti s štirimi popolnimi prirejanji, dopušca ?$P_{12}$?-barvanje. Ti dve novi domnevi imenujeva ?$S_{12}$?-domneva in ?$P_{12}$?-domneva. Najin prvi rezultat opravičuje izbiro grafov v ?$S_{12}$?-domnevi in ?$P_{12}$?-domnevi. Nadalje, karakterizirava povezave v ?$P_{12}$?, ki lahko nastopajo v ?$P_{12}$?-barvanju kubičnega grafa ?$G$?. Nazadnje, poveževa novi domnevi z že znanimi domnevami, ko dokaževa, da ?$S_{12}$?-domneva implicira ?$S_{10}$?-domnevo, in da ?$P_{12}$?-domneva ter ?$(5, 2)$?-ciklična krovna domneva skupaj implicirata ?$P_{10}$?-domnevo. Najino glavno orodje za dokaz zadnje trditve je nova reformulacija ?$(5, 2)$?-ciklične krovne domneve, ki pravi, da se povezavna množica poljubnega brezmostnega kubičpnega grafa brez trizobov da pokriti s štirimi popolnimi prirejanjiTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije