20.500.12556/DKUM-84694 Barvanje povezav grafa z najmanjšim številom palet na študijskem programu Izobraževalna matematika in izobraževalno računalništvo Minimum number of palettes in edge coloring magistrsko delo V magistrskem delu obravnavamo paletno barvanje povezav in paletni indeks različnih družin grafov. Dobro barvanje povezav je barvanje, pri katerem velja, da nobeni incidenčni povezavi nista pobarvani z enako barvo. Dobro barvanje povezav grafa za vsako vozlišče definira množico barv incidenčnih povezav. Takšno množico imenujemo paleta vozlišča. V literaturi se avtorji večinoma osredotočajo na barvanje povezav grafov, pri katerem je uporabljeno največje možno število palet. Mi se bomo osredotočili na iskanje takšnega barvanja povezav grafa, za katerega bo veljalo, da je barvanje dobro in pri katerem bo uporabljeno najmanjše možno število palet, ki ga imenujemo paletni indeks grafa. Na začetku spoznamo osnove teorije grafov, ki nam pomagajo pri nadaljnjem razumevanju teorije. V osrednjem delu magistrske dela ugotovimo, da nas dobro barvanje z najmanjšim številom možnih barv ne pripelje vedno do najmanjšega števila palet. Spoznamo tudi, kako poiskati paletne indekse nekaterih znanih družin grafov in posebnih primerov grafov, pri katerih namesto minimalnega barvanja povezav uporabimo barvanje z večjim številom barv. In the following master's thesis, we discuss the palette coloring of the edges and palette index of different types of graphs. A proper edge coloring of edges is a coloring where no two incident edges are colored with the same color. Proper edge coloring of a graph defines for each node a set of colored edges, which is called a palette of the vertex. In many scientific papers, authors are focusing on finding proper edge coloring with the largest possible number of palettes. However, we will focus on finding a proper edge coloring using the smallest possible number of palettes, which we call the palette index of a graph. At the beginning of the thesis, we are talking about the basics of graph theory, which help us to understand the theory further. In the main part of the master's thesis, we learn that a proper coloring with the smallest number of possible colors does not always lead us to the smallest number of palettes. We also learn how to find the palette index of known graphs and particular examples of graphs where we use a coloring with a larger number of colors than minimal. Barvanje povezav paletno barvanje povezav paletni indeks. Edge coloring palette edge coloring palette index. true true false [K. Bregač] Slovenski jezik Angleški jezik Magistrsko delo/naloga 2023-07-10 14:24:53 2023-09-07 14:01:36 2023-09-08 03:06:22 0000-00-00 00:00:00 2023 0 Maribor 0 Maribor 48 str. 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17(043.2) 163623427 EMAG_Bregac_Karmen_2023.pdf EMAG_Bregac_Karmen_2023.pdf 1 2E4B19379B29AD18F4EF9BF7F05FDF71 863ebb0cd2870fa9907dd17a1fb19b9cab429bd9c9567e0e6aae12184b8abd4c af559846-2fb7-11ee-a26d-00155d000105 https://dk.um.si/Dokument.php?lang=slv&id=169108 Fakulteta za naravoslovje in matematiko 0 0 0