Title: | S-pakovací hranové barvení grafů |
Other Titles: | S-packing edge-colouring of graphs |
Authors: | Baborová, Karolína |
Advisor: | Holub Přemysl, Doc. RNDr. Ph.D. |
Referee: | Ekstein Jan, RNDr. Ph.D. |
Issue Date: | 2022 |
Publisher: | Západočeská univerzita v Plzni |
Document type: | bakalářská práce |
URI: | http://hdl.handle.net/11025/48907 |
Keywords: | hranové barvení;přípustné hranové barvení;silné hranové barvení;distanční hranové barvení;s-pakovací hranové barvení |
Keywords in different language: | edge coloring;proper edge coloring;strong edge coloring;distance edge coloring;s-packing edge coloring |
Abstract: | Práce se zabývá S-pakovacím hranovým barvením grafů. Nechť S = (s_1, s_2, s_3, ...) je neklesající posloupnost přirozených čísel. S-pakovacím hranovým barvením grafu se rozumí funkce f, která přiřazuje hranám grafu G barvy z množiny {1, 2, 3,...} v závislosti na dané sekvenci S tak, že každé dvě hrany obarvené barvou i jsou ve vzájemné vzdálenosti alespoň s_i. S-pakovacím chromatickým indexem, který náleží tomuto barvení, se rozumí minimální počet použitých barev k obarvení grafu právě tímto typem hranového barvení. Část práce je věnována rešerši pro sekvenci S = (1, 1, . . . , 1), nebo-li pro přípustné hranové barvení, dále pro sekvenci S = (2, 2, . . . , 2), nebo-li pro silné hranové barvení, pro sekvenci S = (d, d, . . . , d), nebo-li pro distanční hranové barvení a nakonec obecně pro S-pakovací hranové barvení. Přípustnému hranovému barvení se práce věnuje jen letmo. V této práci byly dále dokázány nové výsledky S-pakovacího chromatického indexu pro sekvence obsahující pouze hodnoty 1 a 2 pro čtvercovou a hexagonální síť. |
Abstract in different language: | The thesis deals with S-packing edge colorings of graphs. For a non-decreasing sequence of positive integers S = (s_1, s_2, s_3, ...), an S-packing edge coloring of a graph is a function f that assigns colors from {1, 2, 3, . . . } to the edges of the graph depending on the sequence S so that the distance between two edges that have color i is at least s_i. The S-packing chromatic index of G is the smallest number of colors needed to color the edges of G by an S-packing edge coloring. First part of the thesis summarizes some known results for sequences S = (1, 1, . . . , 1) (proper edge coloring), S = (2, 2, . . . , 2) (strong edge coloring), S = (d, d, . . . , d) (distance edge coloring) and fi nally for S-packing edge coloring. This thesis brings new results on the S-packing edge coloring of square and hexagonal grids for sequences S that contains only the values 1 and 2. |
Rights: | Plný text práce je přístupný bez omezení |
Appears in Collections: | Bakalářské práce / Bachelor´s works (KMA) |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
karolina_baborova_BP.pdf | Plný text práce | 2,15 MB | Adobe PDF | View/Open |
PO_Baborova.pdf | Posudek oponenta práce | 755,12 kB | Adobe PDF | View/Open |
PV_Baborova.pdf | Posudek vedoucího práce | 633,76 kB | Adobe PDF | View/Open |
prubeh_Baborova.pdf | Průběh obhajoby práce | 201,36 kB | Adobe PDF | View/Open |
Please use this identifier to cite or link to this item:
http://hdl.handle.net/11025/48907
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.