| Title: | Reedova hypotéza pro vrcholové barvení grafů |
| Other Titles: | Reed's conjecture for a vertex colouring of graphs |
| Authors: | Kalvas, Karel Antonín |
| Advisor: | Ekstein Jan, RNDr. Ph.D. |
| Referee: | Holub Přemysl, Doc. RNDr. Ph.D. |
| Issue Date: | 2024 |
| Publisher: | Západočeská univerzita v Plzni |
| Document type: | bakalářská práce |
| URI: | http://hdl.handle.net/11025/57293 |
| Keywords: | vrcholové barvení;reedova hypotéza;chromatické číslo;klikovost;maximální stupeň;zakázané podgrafy |
| Keywords in different language: | vertex coloring;reed's conjecture;chromatic number;clique number;maximum degree;forbidden subgraphs |
| Abstract: | V 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. |
| Abstract in different language: | In 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. |
| 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 | |
|---|---|---|---|---|
| Kalvas - BP.pdf | Plný text práce | 6,66 MB | Adobe PDF | View/Open |
| PV_Kalvas.pdf | Posudek vedoucího práce | 665,8 kB | Adobe PDF | View/Open |
| PO_Kalvas.pdf | Posudek oponenta práce | 1,21 MB | Adobe PDF | View/Open |
| Prubeh_Kalvas.pdf | Průběh obhajoby práce | 172,94 kB | Adobe PDF | View/Open |
Please use this identifier to cite or link to this item:
http://hdl.handle.net/11025/57293Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.