Pakirno barvanje grafa

na študijskem programu 2. stopnje Matematika

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

Povzetek

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.

Ključne besede

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

Podatki

Jezik:	Slovenski jezik
Leto izida:	2021
Tipologija:	2.09 - Magistrsko delo
Organizacija:	UM FNM - Fakulteta za naravoslovje in matematiko
Založnik:	[T. Ličina]
UDK:	519.174(043.2)
COBISS:	90325763
Št. ogledov:	220
Št. prenosov:	19
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	Packing coloring of graphs
Sekundarni povzetek:	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.
Sekundarne ključne besede:	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;
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:	45 str.
ID:	13670534