Celotno kromatično število regularnih grafov z visoko stopnjo vozlišč

magistersko delo

Lidija Prašnički (Avtor), Marko Jakovac (Mentor)

Povzetek

V magistrskem delu je obravnavano celotno kromatično število regularnih grafov z visoko stopnjo vozlišč. Celotno kromatično število grafa je najmanjše število barv, ki jih potrebujemo, da pobarvamo vozlišča in povezave grafa tako, da sosednja ali incidentna elementa nimata enakih barv. Behzad-Vizingova domneva nam poda spodnjo in zgornjo mejo za celotno kromatično število. V magistrskem delu dokažemo, da regularni grafi, ki izpolnjujejo določene pogoje povezane s stopnjo grafa, zadoščajo tej domnevi. V prvem poglavju so definirani nekateri pojmi in navedeni pomembni rezultati iz teorije grafov, ki jih potrebujemo v nadaljevanju. V drugem poglavju so obravnavani grafi sodega reda z visoko stopnjo vozlišč. Najprej so podani pomembni rezultati za poljubne grafe, potem pa je v drugem podpoglavju dokazano, da regularni graf sodega reda z visoko stopnjo vozlišč, ki izpolnjuje določen pogoj, zadošča Behzad-Vizingovi domnevi. V tretjem poglavju so podobno obravnavani tudi poljubni in regularni grafi lihega reda z visoko stopnjo vozlišč.

Ključne besede

celotno kromatično število;regularni grafi;prirejanje grafa;magistrska dela;

Podatki

Jezik:	Slovenski jezik
Leto izida:	2015
Tipologija:	2.09 - Magistrsko delo
Organizacija:	UM FNM - Fakulteta za naravoslovje in matematiko
Založnik:	[L. Prašnički]
UDK:	519.17(043.2)
COBISS:	21251592
Št. ogledov:	1594
Št. prenosov:	129
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	The total chromatic number of regular graphs with high vertex degree
Sekundarni povzetek:	The master's thesis deals with the total chromatic number of regular graphs with high vertex degree. The total chromatic number of a graph is the minimum number of colours that we need to colour the vertices and edges of a graph, in which the adjacent or incident elements are not of the same colour. The Behzad-Vizing conjecture gives the lower and upper bound for the total chromatic number. It is proved that the graphs that satisfy certain conditions related to the degree of graph satisfy this conjecture. In the first chapter some concepts are defined and relevant results from graph theory are mentioned which are needed hereinafter. In the second chapter, the graphs of even order with high vertex degree are discussed. First, results for general graphs are given and later it is proved that the Behzad-Vizing conjecture holds for regular graphs of even order and high degree, that meet certain conditions. The same is done in the third chapter for general and regular graphs of odd order and high vertex degree.
Sekundarne ključne besede:	total chromatic number;regular graph;graph matching;master theses;Univerzitetna in visokošolska dela;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Magistrsko delo/naloga
Komentar na gradivo:	Univ. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo
Strani:	58 f.
ID:	8738984