| Název: | Reedova hypotéza pro vrcholové barvení grafů |
| Další názvy: | Reed's conjecture for a vertex colouring of graphs |
| Autoři: | Kalvas, Karel Antonín |
| Vedoucí práce/školitel: | Ekstein Jan, RNDr. Ph.D. |
| Oponent: | Holub Přemysl, Doc. RNDr. Ph.D. |
| Datum vydání: | 2024 |
| Nakladatel: | Západočeská univerzita v Plzni |
| Typ dokumentu: | bakalářská práce |
| URI: | http://hdl.handle.net/11025/57293 |
| Klíčová slova: | vrcholové barvení;reedova hypotéza;chromatické číslo;klikovost;maximální stupeň;zakázané podgrafy |
| Klíčová slova v dalším jazyce: | vertex coloring;reed's conjecture;chromatic number;clique number;maximum degree;forbidden subgraphs |
| Abstrakt: | 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. |
| Abstrakt v dalším jazyce: | 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. |
| Práva: | Plný text práce je přístupný bez omezení |
| Vyskytuje se v kolekcích: | Bakalářské práce / Bachelor´s works (KMA) |
Soubory připojené k záznamu:
| Soubor | Popis | Velikost | Formát | |
|---|---|---|---|---|
| Kalvas - BP.pdf | Plný text práce | 6,66 MB | Adobe PDF | Zobrazit/otevřít |
| PV_Kalvas.pdf | Posudek vedoucího práce | 665,8 kB | Adobe PDF | Zobrazit/otevřít |
| PO_Kalvas.pdf | Posudek oponenta práce | 1,21 MB | Adobe PDF | Zobrazit/otevřít |
| Prubeh_Kalvas.pdf | Průběh obhajoby práce | 172,94 kB | Adobe PDF | Zobrazit/otevřít |
Použijte tento identifikátor k citaci nebo jako odkaz na tento záznam:
http://hdl.handle.net/11025/57293Všechny záznamy v DSpace jsou chráněny autorskými právy, všechna práva vyhrazena.