|
|
Petersenovské obarvení a jeho varianty
Bílková, Hana ; Šámal, Robert (vedoucí práce) ; Dvořák, Zdeněk (oponent)
Petersenovské obarvení 3-regulárního grafu G je ekvivalentní tzv. normálnímu obarvení za použití pěti barev. Normální obarvení je dobré hranové obarvení ta- kové, že každá hrana je spolu se svými čtyřmi sousedy obarvena dohromady třemi nebo pěti různými barvami. Podle Jaegerovy hypotézy lze každý 3-regulární graf bez mostů petersenovsky obarvit. Platnost hypotézy by dokázala další zajímavá tvrzení pro 3-regulární grafy. V tomto textu se budeme zabývat normálním obar- vením pro větší počet barev. Z Jaegerovy věty o nenulovém Z2 3 -toku plyne, že každý graf bez mostů lze normálně obarvit sedmi barvami. Zde dokážeme exis- tenci obarvení devíti barvami pro grafy s mostem, s řezem velikosti dva nebo s trojúhelníkem nezávisle na Jaegerově větě. Důkaz využívá myšlenku Andersenova důkazu existence silného hranového obarvení 3-regulárních grafů deseti barvami. V závěru řekneme, jak by mohl jít důkaz dokončit pro zbylé třídy 3-regulárních grafů. 1
|
|
|
Variants of Petersen coloring for some graph classes
Bílková, Hana ; Šámal, Robert (vedoucí práce) ; Rollová, Edita (oponent)
Normální obarvení - ekvivalentní verze petersenovského obarvení - je speciální dobré hranové obarvení kubických grafů pěti barvami. Každá hrana normálně obarveného grafu je normální, tj. používá spolu se svými čtyřmi sousedy pouze tři barvy nebo všech pět barev. Dle Jaegerovy hypotézy mají všechny kubické grafy bez mostů normální obarvení. Platnost hypotézy by dokázala například hy- potézu Cycle double cover. Zde řešíme slabší verzi Jaegerova problému. Hledáme dobré hranové pěti-obarvení takové, že alespoň část hran je normální. Pro obecné hranoly (generalized prisms) ukážeme obarvení s dvěma třetinami normálních hran, pro grafy bez krátkých kružnic obarvení s necelou polovinou normálních hran. Dále navrhneme nový pohled na normální obarvení - řetízky (chains). Po- mocí nich dokážeme tvrzení o nemožnosti výskytu právě jedné chyby ve skoro normálním obarvení a také několik tvrzení o řezech v normálně obarveném grafu plynoucí rovněž z nikde-nulového Petersenova toku. Nakonec prozkoumáme čtyř- cyklus v normálně obarveném grafu.
|
|
|
Petersenovské obarvení a jeho varianty
Bílková, Hana ; Šámal, Robert (vedoucí práce) ; Dvořák, Zdeněk (oponent)
Petersenovské obarvení 3-regulárního grafu G je ekvivalentní tzv. normálnímu obarvení za použití pěti barev. Normální obarvení je dobré hranové obarvení ta- kové, že každá hrana je spolu se svými čtyřmi sousedy obarvena dohromady třemi nebo pěti různými barvami. Podle Jaegerovy hypotézy lze každý 3-regulární graf bez mostů petersenovsky obarvit. Platnost hypotézy by dokázala další zajímavá tvrzení pro 3-regulární grafy. V tomto textu se budeme zabývat normálním obar- vením pro větší počet barev. Z Jaegerovy věty o nenulovém Z2 3 -toku plyne, že každý graf bez mostů lze normálně obarvit sedmi barvami. Zde dokážeme exis- tenci obarvení devíti barvami pro grafy s mostem, s řezem velikosti dva nebo s trojúhelníkem nezávisle na Jaegerově větě. Důkaz využívá myšlenku Andersenova důkazu existence silného hranového obarvení 3-regulárních grafů deseti barvami. V závěru řekneme, jak by mohl jít důkaz dokončit pro zbylé třídy 3-regulárních grafů. 1
|
host ::
RSS.