| Abstrakt: | Berge-Fulkersonova hypotéza hovorí, že v každom bezmostovom kubickom grafe $G$
existuje šesť $1$-faktorov takých, že každá hrana grafu $G$ sa nachádza v práve
dvoch z týchto $1$-faktorov. Keďže táto podmienka je triviálne splnená pre
hranovo $3$-zafarbiteľné grafy, zaujímavé je v tejto súvislosti študovať
bezmostové kubické grafy s chromatickým indexom štyri, takzvané snarky.
V tejto práci zhrnieme niektoré nedávno publikované poznatky o tejto hypotéze,
a ukážeme pomocou týchto poznatkov platnosť hypotézy pre triedy grafov, pre
ktoré hypotéza nebola doteraz overená. Ukážeme, že hypotéza platí pre obe
triedy zovšeobecnených Blanušovych snarkov a triedu zovšeobecnených
Szekeresovych snarkov, ako aj pre niektoré triedy snarkov skonštruované pomocou
súčinu kubických grafov.
|
|---|