Barvanje povezav 4-valentnih grafov

diplomsko delo

Nika Molan (Author), Arjana Žitnik (Mentor)

Abstract

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.

Keywords

graf;barvanje povezav;4-valentni grafi;grafi razreda I;grafi razreda II;snarki;univerzitetni študij;diplomske naloge;

Data

Language:	Slovenian
Year of publishing:	2023
Typology:	2.11 - Undergraduate Thesis
Organization:	UL FRI - Faculty of Computer and Information Science
Publisher:	[N. Molan]
UDC:	519.17:004(043.2)
COBISS:	165672451
Views:	96
Downloads:	19
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	Edge-colouring of 4-valent graphs
Secondary 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.
Secondary keywords:	graph;edge colouring;4-regular graphs;class I graphs;class II graphs;snarks;mathematics;computer science;computer and information science;computer science and mathematics;interdisciplinary studies;diploma;Teorija grafov;Matematika;Računalništvo;Univerzitetna in visokošolska dela;
Type (COBISS):	Bachelor thesis/paper
Study programme:	1000407
Embargo end date (OpenAIRE):	1970-01-01
Thesis comment:	Univ. v Ljubljani, Fak. za računalništvo in informatiko
Pages:	46 str.
ID:	19912978