Barvanje povezav 4-valentnih grafov

Molan, Nika (author), Žitnik, Arjana (mentor)

V 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.

• Language: Slovenian
• Keywords: graf, barvanje povezav, 4-valentni grafi, grafi razreda I, grafi razreda II, snarki
• Work type: Bachelor thesis/paper
• Typology: 2.11 - Undergraduate Thesis
• Organization: FRI - Faculty of Computer and Information Science ; FMF - Faculty of Mathematics and Physics
• Year: 2023
• PID: 20.500.12556/RUL-149709
• COBISS.SI-ID: 165672451
• Publication date in RUL: 08.09.2023

Secondary language

• Language: English
• Title: Edge-colouring of 4-valent graphs

Abstract

This thesis deals with the concept of edge-colouring 4-regular graphs. The first part presents all the terminology we will use, focusing on the edge-colouring problem. Vizing’s theorem, which partitions graphs into classes I and II, is proved along with some other theorems that determine the class for some graph families. For example, all bipartite graphs are of class I, regular graphs with an odd number of vertices are of class II and regular connected graphs with a cut vertex are of class II. Second part investigates snarks, especially the Petersen graph, and important properties of 4-regular graphs. It is shown that edges of 4-regular graphs can be partitioned into two disjoint 2-factors, which is an important property for further research on edge-colouring. It turns out that 4-regular graphs whose edges can be partitioned into two disjoint even 2-factors are of class I. Additionally it is proven that in a 4-regular graph that has K5 − e as a subgraph no such partitioning of edges exists, which offers a simple construction for infinite families of 4-regular class II graphs. It is shown that line graphs of snarks are class II and line graphs of other cubic graphs that are not snarks are class I. Last but not least, some constructions of 4-regular class II graphs are given.

• Keywords: graph, edge colouring, 4-regular graphs, class I graphs, class II graphs, snarks