Title: Distanční barvení grafů
Other Titles: Distance colouring of graphs
Authors: Supíková, Tereza
Advisor: Holub Přemysl, Doc. RNDr. Ph.D.
Referee: Ekstein Jan, RNDr. Ph.D.
Issue Date: 2018
Publisher: Západočeská univerzita v Plzni
Document type: bakalářská práce
URI: http://hdl.handle.net/11025/32346
Keywords: 2-distanční barvení;seznamové 2-distanční barvení;2-distanční chromatické číslo;seznamové 2-distanční chromatické číslo;zobecněné petersenovy grafy
Keywords in different language: 2-distance vertex colouring;list 2-distance vertex colouring;2-distance chromatic number;list 2-distance chromatic number;generalized petersen graphs
Abstract: Vrcholové 2-distanční barvení grafu G je zobrazení f: V(G) -> N, pro které platí, že f(u) je různé od f(v) pro každé u,v z V(G) s dist_G(u,v) <= 2. Hodnotu f(u) nazýváme barvou vrcholu u. Nejmenší počet barev nutných k 2-distančnímu obarvení grafu G nazýváme 2-distanční chromatické číslo grafu a značíme chi^2(G). Cílem této bakalářské práce je vytvořit ucelený přehled dosud známých výsledků ohledně 2-distančního barvení grafů, zejména rovinných. Do přehledu zahrneme i seznamové 2-distanční barvení. Pro seznamové 2-distanční chromatické číslo, značíme chi^2_l(G), totiž platí chi^2_l(G) >= chi^2 (G). Tedy je-li dokázána nějaká horní mez pro seznamové 2-distanční chromatické číslo, potom tato mez jistě platí také pro 2-distanční chromatické číslo. Výsledky přehledně rozdělíme do kapitol na základě dvou kritérií. Jedním z kritérií je určení horní meze 2-distančního chromatického čísla a seznamového 2-distančního chromatického čísla. Druhým kritériem je rovnost 2-distančního chromatického čísla nebo seznamového 2-distančního chromatického čísla nejmenší možné hodnotě, tedy číslu Delta(G) + 1. V druhé části bakalářské práce se už věnujeme výhradně 2-distančnímu barvení zobecněných Petersenových grafů. Nejprve se zabýváme zobecněnými Petersenovy grafy s malým počtem vrcholů. Pro každý takový graf určíme hodnotu 2-distančního chromatického čísla, navrhneme vhodné 2-distanční obarvení grafu G a doplníme obrázkem. Na základě těchto poznatků zformulujeme a poté dokážeme tvrzení, která určují hodnotu 2-distančního chromatického čísla zobecněných Petersenových grafů s libovolně velkým počtem vrcholů, které splňují určitou podmínku.
Abstract in different language: A vertex colouring f: V(G) -> N, of a graph G is called a 2-distance vertex colouring if every pair of vertices at distance at most two have different colours. That means f(u) is not equal f(v) for all u,v from V(G) with dist_G(u,v) <= 2. The value f(u) is called a colour of vertex u. The minimum number of colours in a 2-distance colouring of a graph G is called the 2-distance chromatic number, denoted by chi^2(G). The main aim of this Bachelor thesis is to create comprehensive overview of known results regarding 2-distance colouring of graphs, especially planar graphs. It also includes a list 2-distance colouring, because for the list 2-distance chromatic number, denoted by chi^2_l(G), we have chi^2_l(G) >= chi^2 (G). Hence if some upper bound is proven for the list 2-distance chromatic number, then it also holds for the 2-distance chromatic number. The results are clearly divided into several chapters based on two criteria. One of them is to determine upper bounds for the 2-distance chromatic number and the list 2-distance chromatic number. The second criterion is the equality between the 2-distance chromatic number, or the list 2-distance chromatic number, respectively, and the smallest possible value Delta(G) + 1. In the second part of this Bachelor thesis, we focus on 2-distance colourings of generalized Petersen graphs. First we deal with generalized Petersen graphs of small order. For each of these graphs we determine the value of the 2-distance chromatic number, suggest appropriate 2-distance colouring and attach a picture. Based on this knowledge we derive the 2-distance chromatic number of generalized Petersen graphs with arbitrarily large number of vertices, with some additional condition.
Rights: Plný text práce je přístupný bez omezení.
Appears in Collections:Diplomové práce / Theses (KMA)

Files in This Item:
File Description SizeFormat 
Bakalarska prace.pdfPlný text práce8,69 MBAdobe PDFView/Open
PV_Supikova.pdfPosudek vedoucího práce982,37 kBAdobe PDFView/Open
PO_Supikova.pdfPosudek oponenta práce1,33 MBAdobe PDFView/Open
OB_Supikova.pdfPrůběh obhajoby práce260,33 kBAdobe PDFView/Open


Please use this identifier to cite or link to this item: http://hdl.handle.net/11025/32346

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.