Barvanje povezav 4-valentnih grafovMolan, Nika (Avtor) Žitnik, Arjana (Mentor) grafbarvanje povezav4-valentni grafigrafi razreda Igrafi razreda IIsnarkiV diplomski nalogi obravnavamo barvanje povezav 4-valentnih grafov. V prvem delu je predstavljena vsa terminologija, ki jo bomo uporabljali, s poudarkom na problemu barvanja povezav. Dokazan je Vizingov izrek, ki grafe razdeli na razreda I in II ter nekaj drugih izrekov, ki posameznim družinam grafov določijo ustrezen razred. Med drugim je dokazano, da so vsi dvodelni grafi razreda I, regularni grafi na liho mnogo vozliščih so razreda II in regularni povezani grafi s prereznim vozliščem so razreda II. V drugem delu so predstavljeni kubični grafi razreda II, tako imenovani snarki, posebno Petersenov graf ter pomembne lastnosti 4-valentnih grafov. Dokazano je, da lahko 4-valentnim grafom povezave razdelimo na dva disjunktna 2-faktorja, kar je pomembna ugotovitev za nadaljno raziskovanje barvanja povezav. Izkaže se namreč, da je poljuben 4-valenten graf, katerega povezave lahko razdelimo v dva disjunktna soda 2-faktorja, razreda I. Sledi ugotovitev, da v 4-valentnem grafu, ki premore K5 − e kot podgraf, taka razdelitev povezav ne obstaja, kar ponuja enostavno konstrukcijo neskončne družine 4-valentnih grafov razreda II. Dokazano je, da so povezavni grafi snarkov razreda II, povezavni grafi ostalih kubičnih grafov, ki niso snarki, pa razreda I. Nenazadnje pa so podane tudi konstrukcije predstavnikov 4-valentih grafov razreda II.20232023-09-08 12:10:00Diplomsko delo/naloga149709VisID: 36621COBISS_ID: 165672451sl