Full metadata record
DC FieldValueLanguage
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
Appears in Collections:Bakalářské práce / Bachelor´s works (KMA)

Files in This Item:
File Description SizeFormat 
Kalvas - BP.pdfPlný text práce6,66 MBAdobe PDFView/Open
PV_Kalvas.pdfPosudek vedoucího práce665,8 kBAdobe PDFView/Open
PO_Kalvas.pdfPosudek oponenta práce1,21 MBAdobe PDFView/Open
Prubeh_Kalvas.pdfPrůběh obhajoby práce172,94 kBAdobe PDFView/Open
Show simple item record


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

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

search
navigation
  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)