Petersenovské obarvení a jeho varianty
| Thesis title in Czech: | Petersenovské obarvení a jeho varianty |
|---|---|
| Thesis title in English: | Petersen coloring and variants |
| Key words: | grafy, cykly, nenulové toky, hranové barvení |
| English key words: | graphs, cycles, nowhere-zero flows, edge colorings |
| Academic year of topic announcement: | 2011/2012 |
| Thesis type: | Bachelor's thesis |
| Thesis language: | čeština |
| Department: | Department of Applied Mathematics (32-KAM) |
| Supervisor: | doc. Mgr. Robert Šámal, Ph.D. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 10.11.2011 |
| Date of assignment: | 11.11.2011 |
| Confirmed by Study dept. on: | 09.01.2012 |
| Date and time of defence: | 18.06.2012 00:00 |
| Date of electronic submission: | 24.05.2012 |
| Date of submission of printed version: | 24.05.2012 |
| Date of proceeded defence: | 18.06.2012 |
| Opponents: | prof. Mgr. Zdeněk Dvořák, Ph.D. |
| Guidelines |
| Cílem práce je prozkoumat různé varianty Jaegerova problému
tzv. Petersenovského obarvení. Petersenovské obarvení lze definovat takto: chceme hrany 3-regulárního grafu obarvit pomocí pěti barev tak, že se jedná o korektní hranové barvení a navíc je každá hrana bohatá nebo chudá: Hranu nazveme bohatou, pokud ona a její 4 sousední hrany mají dohromady 5 barev; nazveme ji chudou, pokud na ní a jejích sousedech jsou jen 3 barvy. Hypotéza od pana Jaegera [viz citovaný článek] tvrdí, že každý 3-regulární graf bez mostů lze výše popsaným způsobem obarvit. Pokud je tato hypotéza pravdivá, tak z ní plyne řešení mnoha dalších otevřených problémů. Podle zájmu řešitele(-lky) je možné práci zaměřovat více experimentálně (hledání různých obarvení na počítači) nebo více teoreticky, případně oba přístupy propojit. |
| References |
| François Jaeger: On five-edge-colorings of cubic graphs and nowhere-zero flow problems. Ars Combin. 20 (1985), B, 229–244
Petersen coloring conjecture, http://garden.irmacs.sfu.ca/?q=op/petersen_coloring_conjecture Cun-Quan Zhang: Integer flows and cycle covers of graphs. Monographs and Textbooks in Pure and Applied Mathematics, 205. Marcel Dekker, Inc., New York, 1997. Další časopisecká literatura podle pokynů vedoucího |
| Preliminary scope of work |
| Petersenovské obarvení lze definovat takto: chceme hrany
3-regulárního grafu obarvit pomocí pěti barev tak, že se jedná o korektní hranové barvení a navíc je každá hrana bohatá nebo chudá: Hranu nazveme bohatou, pokud ona a její 4 sousední hrany mají dohromady 5 barev; nazveme ji chudou, pokud na ní a jejích sousedech jsou jen 3 barvy. Hypotéza od pana Jaegera [viz citace] tvrdí, že každý 3-regulární graf bez mostů lze výše popsaným způsobem obarvit. Pokud je tato hypotéza pravdivá, tak z ní plyne řešení mnoha dalších otevřených problémů. Cílem bakalářky není nutně problém vyřešit (k tomu patrně nedojde), ale zkoumat problémy touto hypotézou motivované a tím částečně k přispět k jejímu vyřešení v budoucnu. Podle zájmu studenta je možné práci zaměřovat více experimentálně (hledání různých obarvení na počítači) nebo více teoreticky, případně oba přistupy propojit. |