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

angleški

2019

letnik 17, številka 2

?$S_{10}$?-domneva   domneva o petersenskem barvanju   kubični graf   Petersenov graf

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

Č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 prirejanji.

29.05.2020