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ů Variants of Petersen coloring for some graph classes graphs, cycles, nowhere-zero flows, edge colorings graphs, cycles, nowhere-zero flows, edge colorings 2013/2014 diplomová práce angličtina Informatický ústav Univerzity Karlovy (32-IUUK) doc. Mgr. Robert Šámal, Ph.D. skrytý - zadáno a potvrzeno stud. odd. 03.07.2014 10.07.2014 18.07.2014 03.06.2015 09:00 04.05.2015 05.05.2015 03.06.2015 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 altogether. 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.