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 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. |