Petersenovské obarvení a jeho varianty

• Název práce v češtině: Petersenovské obarvení a jeho varianty
• Název v anglickém jazyce: Petersen coloring and variants
• Klíčová slova: grafy, cykly, nenulové toky, hranové barvení
• Klíčová slova anglicky: graphs, cycles, nowhere-zero flows, edge colorings
• Akademický rok vypsání: 2011/2012
• Typ práce: bakalářská práce
• Jazyk práce: čeština
• Ústav: Katedra aplikované matematiky (32-KAM)
• Vedoucí / školitel: doc. Mgr. Robert Šámal, Ph.D.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 10.11.2011
• Datum zadání: 11.11.2011
• Datum potvrzení stud. oddělením: 09.01.2012
• Datum a čas obhajoby: 18.06.2012 00:00
• Datum odevzdání elektronické podoby: 24.05.2012
• Datum odevzdání tištěné podoby: 24.05.2012
• Datum proběhlé obhajoby: 18.06.2012
• Oponenti: prof. Mgr. Zdeněk Dvořák, Ph.D.

Zásady pro vypracování

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.

Seznam odborné literatury

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

Předběžná náplň práce

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.