Full metadata record
DC poleHodnotaJazyk
dc.contributor.advisorEkstein Jan, RNDr. Ph.D.
dc.contributor.authorKalvas, Karel Antonín
dc.contributor.refereeHolub Přemysl, Doc. RNDr. Ph.D.
dc.date.accepted2024-6-17
dc.date.accessioned2024-07-12T09:15:07Z-
dc.date.available2023-10-2
dc.date.available2024-07-12T09:15:07Z-
dc.date.issued2024
dc.date.submitted2024-5-22
dc.identifier96886
dc.identifier.urihttp://hdl.handle.net/11025/57293-
dc.description.abstractV této práci se seznámíme s vrcholovým barvením grafů. Následně představíme Reedovu hypotézu (B. Reed. omega, Delta, and chi), která dává horní odhad na chromatické číslo grafu G jako chi(G) <= ceil((omega(G) + Delta(G)+1)/2). Následně shrneme doposud známé výsledky z oblasti Reedovy hypotézy a zaměříme se na výsledky které, uveřejnili Aravind a kol. v článku Bounding chi in terms of omega and Delta for some classes of graphs, kde mimo jiné ukázali, že třída {Chair, House, Bull, K_1+C_4}-free grafů a třída {Chair, House, Bull, Dart}-free grafů splňuje Reedovu hypotézu. Ve snaze o oslabení požadavku na počet zakázaných podgrafů v rámci vlastních výsledků uvedeme třídu grafů, která splňuje Reedovu hypotézu a rozšiřuje výše zmíněné výsledky.cs
dc.format28 s.
dc.language.isocs
dc.publisherZápadočeská univerzita v Plzni
dc.rightsPlný text práce je přístupný bez omezení
dc.subjectvrcholové barvenícs
dc.subjectreedova hypotézacs
dc.subjectchromatické číslocs
dc.subjectklikovostcs
dc.subjectmaximální stupeňcs
dc.subjectzakázané podgrafycs
dc.titleReedova hypotéza pro vrcholové barvení grafůcs
dc.title.alternativeReed's conjecture for a vertex colouring of graphsen
dc.typebakalářská práce
dc.thesis.degree-nameBc.
dc.thesis.degree-levelBakalářský
dc.thesis.degree-grantorZápadočeská univerzita v Plzni. Fakulta aplikovaných věd
dc.thesis.degree-programMatematika a její aplikace
dc.description.resultObhájeno
dc.description.abstract-translatedIn this work, we will introduce the concept of vertex colouring of graphs. Subsequently, we will present Reed's conjecture (B. Reed. omega, Delta, and chi), which provides an upper bound on the chromatic number of a graph G, expressed as chi(G) <= ceil((omega(G) + Delta(G)+1)/2). Following that we will then summarize the known results in the area of Reed's conjecture and focus on the results published by Aravind et al. in article Bounding chi in terms of omega and Delta for some classes of graphs, where they proved that the class of {Chair, House, Bull, K_1+C_4}-free graphs and the class of {Chair, House, Bull, Dart}-free graphs satisfy Reed's conjecture. In an attempt to weaken the requirement on the number of forbidden subgraphs within our own results, we will introduce a class of graphs that satisfies Reed's conjecture and extends the aforementioned results.en
dc.subject.translatedvertex coloringen
dc.subject.translatedreed's conjectureen
dc.subject.translatedchromatic numberen
dc.subject.translatedclique numberen
dc.subject.translatedmaximum degreeen
dc.subject.translatedforbidden subgraphsen
Vyskytuje se v kolekcích:Bakalářské práce / Bachelor´s works (KMA)

Soubory připojené k záznamu:
Soubor Popis VelikostFormát 
Kalvas - BP.pdfPlný text práce6,66 MBAdobe PDFZobrazit/otevřít
PV_Kalvas.pdfPosudek vedoucího práce665,8 kBAdobe PDFZobrazit/otevřít
PO_Kalvas.pdfPosudek oponenta práce1,21 MBAdobe PDFZobrazit/otevřít
Prubeh_Kalvas.pdfPrůběh obhajoby práce172,94 kBAdobe PDFZobrazit/otevřít
Zobrazit minimální záznam Zobrazit statistiky


Použijte tento identifikátor k citaci nebo jako odkaz na tento záznam: http://hdl.handle.net/11025/57293

Všechny záznamy v DSpace jsou chráněny autorskými právy, všechna práva vyhrazena.

hledání
navigace
  1. DSpace at University of West Bohemia
  2. Vysokoškolské kvalifikační práce / Theses
  3. Fakulta aplikovaných věd / Faculty of Applied Sciences
  4. Katedra matematiky / Department of Mathematics
  5. Bakalářské práce / Bachelor´s works (KMA)