Témata prací (Výběr práce)Témata prací (Výběr práce)(verze: 348)
Detail práce
   Přihlásit přes CAS
Variants of Petersen coloring for some graph classes
Název práce v češtině: Varianty petersenovského obarvení pro některé třídy grafů
Název v anglickém jazyce: Variants of Petersen coloring for some graph classes
Klíčová slova: graphs, cycles, nowhere-zero flows, edge colorings
Klíčová slova anglicky: graphs, cycles, nowhere-zero flows, edge colorings
Akademický rok vypsání: 2013/2014
Typ práce: diplomová práce
Jazyk práce: angličtina
Ústav: Informatický ústav Univerzity Karlovy (32-IUUK)
Vedoucí / školitel: doc. Mgr. Robert Šámal, Ph.D.
Řešitel: skrytý - zadáno a potvrzeno stud. odd.
Datum přihlášení: 03.07.2014
Datum zadání: 10.07.2014
Datum potvrzení stud. oddělením: 18.07.2014
Datum a čas obhajoby: 03.06.2015 09:00
Datum odevzdání elektronické podoby:04.05.2015
Datum odevzdání tištěné podoby:05.05.2015
Datum proběhlé obhajoby: 03.06.2015
Oponenti: RNDr. Edita Rollová, Ph.D.
Zásady pro vypracování
Petersen coloring can be defined as follows: we want to properly color the edges of a 3-regular graph using five colors, so that every edge is either rich or poor:
We call an edge rich (in a particular coloring) if it together with its 4 adjacent edges have all 5 colors; we call it poor if it and its neighbors use only 3 colors

Jaeger conjectured [2] that every 3-regular bridgeless graph can be colored as above. If this conjecture is true, many important open problems would follow (see also [5]).

The topic of the thesis is to study various techniques to approach this problem and its natural weakenings, possibly on appropriate graph classes.
One possible variant (suggested in [3]) is to consider prisms (graphs with 2n vertices made of two cycles of length n and a matching in-between them). For such graphs
we want to find a weaker version of Petersen coloring: we only ask the edges on circles to be rich or poor.
Seznam odborné literatury
[1] Cun-Quan Zhang: Circuit double cover of graphs, London Mathematical Society Lecture Note Series, vol. 399, Cambridge University Press, Cambridge, 2012.

[2] François Jaeger: On five-edge-colorings of cubic graphs and nowhere-zero flow problems, Ars Combin. 20 (1985), no. B, 229–244.

[3] Robert Šámal: New approach to Petersen coloring, Electronic Notes in Discrete Mathematics 38: 755-760 (2011), Eurocomb 2011 -- Budapest.

[4] Jonas Hägglund, Eckhard Steffen: Petersen-colorings and some families of snarks, Ars Math. Contemp. 7 (2014), no. 1, 161–173.

[5] Petersen coloring conjecture, http://www.openproblemgarden.org/?q=op/petersen_coloring_conjecture

Further papers based on suggestions of the advisor.
Univerzita Karlova | Informační systém UK