Povezavno 3-obarvljivi grafi

diplomsko delo

Nina Šere (Author), Primož Šparl (Mentor)

Abstract

V diplomskem delu se ukvarjamo s kromatičnim indeksom kubičnih grafov, kjer se omejimo na večji del dobro znane družine takšnih grafov, znanih pod imenom posplošeni Petersenovi grafi. Graf Γ je k-povezavno obarvljiv, če se da njegove povezave obarvati s k barvami tako, da so incidenčne povezave obarvane z različnimi barvami. Najmanjše tako število k imenujemo kromatični indeks grafa in ga označimo χ'(Γ). Ker so posplošeni Petersenovi grafi kubični, ima vsak izmed njih po dobro znanem Vizingovem izreku kromatični indeks bodisi enak 3 bodisi 4. Rezultati tega diplomskega dela predstavljajo pomemben del dokaza, da je znameniti Petersenov graf edini posplošeni Petersenov graf, ki ni povezavno 3-obarvljiv. Z drugimi besedami, Petersenov graf GP(5,2) je edini posplošeni Petersenov graf s kromatičnim indeksom 4.

Keywords

barvanje povezav;kromatični indeks;kubični graf;posplošeni Petersenov graf;

Data

Language:	Slovenian
Year of publishing:	2017
Typology:	2.11 - Undergraduate Thesis
Organization:	UL PEF - Faculty of Education
Publisher:	[N. Šere]
UDC:	519.17(043.2)
COBISS:	11704905
Views:	792
Downloads:	215
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	3–edge colorable graphs
Secondary abstract:	In this BSc thesis we deal with chromatic index of cubic graphs, where we mainly focus on a significant part of the family of graphs, named generalized Petersen graphs. A graph Γ is said to be k-edge-colorable, if we can color its edges with k colors, so that incident edges are colored with different colors. The smallest such number k is called the chromatic index and it is denoted by χ'(Γ). Due to the fact that generalized Petersen graphs are cubic graphs, Vizing's theorem implies that their chromatic index is either 3 or 4. The results of this BSc thesis represent an important part of the proof, that the famous Petersen graph is the only generalized Petersen graph, which is not 3-edge colorable. In other words, the Petersen graph GP(5,2) is the only generalized Petersen graph, whose chromatic index equals 4.
Secondary keywords:	mathematics;matematika;
File type:	application/pdf
Type (COBISS):	Bachelor thesis/paper
Thesis comment:	Univ. v Ljubljani, Pedagoška fak., Dvopredmetni učitelj: matematika-računalništvo
Pages:	V, 29 str.
ID:	10864372