Pakirno barvanje grafa

na študijskem programu 2. stopnje Matematika

Tomaž Ličina (Author), Tanja Gologranc (Mentor)

Abstract

Pakirno barvanje grafa je dobro barvanje vozlišč, pri katerem sta poljubni dve vozlišči z isto barvo i na razdalji večji kot i. Pakirno kromatično število je najmanjše število barv, ki jih potrebujemo za tako barvanje grafa. V magistrskem delu obravnavamo pakirno kromatično število nekaterih družin grafov in zvezo pakirnega kromatičnega števila z drugimi grafovskimi invariantami. Podrobneje obravnavamo zvezo med kličnim, kromatičnim in pakirnim kromatičnim številom. V prvem delu proučujemo pakirno kromatično število na osnovnih družinah grafov, na drevesih, kartezičnih produktih grafov in na grafih Mycielskega. V naslednjem delu obravnavamo grafe z majhnimi pakirnimi kromatičnimi števili in pokažemo, da je preveriti, ali ima graf pakirno kromatično število enako 4, NP-težek problem. V tretjem delu prikažemo zvezo pakirnega kromatičnega števila z neodvisnostnim številom grafa, najmanjšim vozliščnim pokritjem grafa in maksimalno stopnjo v grafu. V zadnjem delu raziskujemo zvezo med kličnim, kromatičnim in pakirnim kromatičnim številom. Poiščemo trojice naravnih števil (a,b,c) za katere obstaja graf G s kličnim številom a, kromatičnim številom b in pakirnim kromatičnim številom c.

Keywords

magistrska dela;barvanje grafov;pakirno barvanje grafov;drevesa;grafi Mycielskega;kartezični produkt grafov;klično število;neodvisnostno število;vozliščno pokritje;

Data

Language:	Slovenian
Year of publishing:	2021
Typology:	2.09 - Master's Thesis
Organization:	UM FNM - Faculty of Natural Sciences and Mathematics
Publisher:	[T. Ličina]
UDC:	519.174(043.2)
COBISS:	90325763
Views:	220
Downloads:	19
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	Packing coloring of graphs
Secondary abstract:	Packing coloring of a graph is a proper vertex coloring, where two different vertices with the same color i, are at a distance greater than i. The packing chromatic number of a graph is the smallest number of colors needed to color a graph with such a coloring. In this masters thesis we study the packing chromatic number of certain families of graphs and the relationship between the packing chromatic number and other graph invariants. We investigate the relationship between the clique, the chromatic and the packing chromatic number. In the first part we study the packing chromatic number of basic families of graphs, such as trees, Cartesian products of graphs and on Mycielskian graphs. In the next part we look at graphs with small packing chromatic numbers and show that the problem of checking if a graph is 4 - packing chromatic colorable is NP-hard. In the third part we investigate the relationship between the packing chromatic number and three other graph invariants, the independance number, the smallest vertex cover of a graph and the maximal vertex degree of a graph. In the last part we present the relationship between the clique number, the chromatic number and the packing chromatic number. We present triples (a,b,c) for which there is a graph G with the clique number a, the chromatic number b and the packing chromatic number c.
Secondary keywords:	master theses;graph coloring;packing coloring of graphs;trees;Mycielskian construction;Cartesian products of graphs;clique number;independance number;vertex cover;Grafične metode;Barvanje grafov;Univerzitetna in visokošolska dela;
Type (COBISS):	Master's thesis/paper
Thesis comment:	Univ. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo
Pages:	45 str.
ID:	13670534