VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
PDF
  • ▫$S_{12}$▫ and ▫$P_{12}$▫-colorings of cubic graphs
    Hakobyan, Anush ; Mkrtchyan, Vahan
    Č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.
    Vir: Ars mathematica contemporanea. - ISSN 1855-3966 (Vol. 17, no. 2, 2019, str. 431-445)
    Vrsta gradiva - članek, sestavni del ; neleposlovje za odrasle
    Leto - 2019
    Jezik - angleški
    COBISS.SI-ID - 18957401

    Povezava(-e):

    https://amc-journal.eu/index.php/amc/article/download/1758/1396
    Digitalna knjižnica Slovenije - dLib.si
    DOI

Vnos na polico