An equivalent formulation of the Fan-Raspaud Conjecture and related problems

angleški

2020

letnik 18, številka 1

Berge-Fulkersonova domneva   Fan-Raspaudova domneva   kubični graf   nenavadnost   Petersenovo barvanje   popolno prirejanje

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

Leta 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 mostove.

28.04.2021