325 KB45 KB200820252020Mazzuoccolo, GiuseppeZerafa, Jean Paulštevilka:1letnik:18str. 87-103ISSN:1855-3966COBISSID_HOST:39151363URN:URN:NBN:SI:doc-OYBOMZPOenUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporaneaBerge-Fulkerson conjectureBerge-Fulkersonova domnevacubic graphFan-Raspaud conjectureFan-Raspaudova domnevakubični grafnenavadnostoddnessperfect matchingPetersen colouringPetersenovo barvanjepopolno prirejanjeAn equivalent formulation of the Fan-Raspaud Conjecture and related problems|In 1994, it was conjectured by Fan and Raspaud J. Comb. Theory, Ser. B 61, No. 1, 133-138 (1994) that every simple bridgeless cubic graph has three perfect matchings whose intersection is empty. In this paper we answer a question recently proposed by Mkrtchyan and Vardanyan, by giving an equivalent formulation of the Fan-Raspaud Conjecture. We also study a possibly weaker conjecture originally proposed by the first author, which states that in every simple bridgeless cubic graph there exist two perfect matchings such that the complement of their union is a bipartite graph. Here, we show that this conjecture can be equivalently stated using a variant of Petersen-colourings, we prove it for graphs having oddness at most four and we give a natural extension to bridgeless cubic multigraphs and to certain cubic graphs having bridgesLeta 1994 sta Fan in Raspaud J. Comb. Theory, Ser. B 61, No. 1, 133-138 (1994) postavila domnevo, da ima vsak enostavni brezmostni kubični graf tri popolna prirejanja, katerih presek je prazen. V tem članku odgovorimo na vprašanje, ki sta ga nedavno zastavila Mkrtchyan in Vardanyan, in sicer tako, da predstavimo ekvivalentno formulacijo Fan-Raspaudove domneve. Preučujemo tudi možno šibkejšo domnevo, ki jo je prvotno predstavil prvi avtor, češ da v vsakem enostavnem brezmostnem kubičnem grafu obstajata taki dve popolni prirejanji, da je komplement njune unije dvodelen graf. Pokažemo, da se da to domnevo enakovredno izraziti s pomočjo različice Petersenovih barvanj, dokažemo jo za grafe, katerih nenavadnost znaša največ štiri, predstavimo pa tudi njeno naravno razširitev na brezmostne kubične multigrafe in na določene kubične grafe, ki premorejo mostoveTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije