magistersko delo
Lidija Prašnički (Author), Marko Jakovac (Mentor)

Abstract

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šč.

Keywords

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

Data

Language: Slovenian
Year of publishing:
Typology: 2.09 - Master's Thesis
Organization: UM FNM - Faculty of Natural Sciences and Mathematics
Publisher: [L. Prašnički]
UDC: 519.17(043.2)
COBISS: 21251592 Link will open in a new window
Views: 1594
Downloads: 129
Average score: 0 (0 votes)
Metadata: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Other data

Secondary language: English
Secondary title: The total chromatic number of regular graphs with high vertex degree
Secondary abstract: 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.
Secondary keywords: total chromatic number;regular graph;graph matching;master theses;Univerzitetna in visokošolska dela;
URN: URN:SI:UM:
Type (COBISS): Master's thesis/paper
Thesis comment: Univ. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo
Pages: 58 f.
ID: 8738984