Variants of Petersen coloring for some graph classes

• Thesis title in Czech: Varianty petersenovského obarvení pro některé třídy grafů
• Thesis title in English: Variants of Petersen coloring for some graph classes
• Key words: graphs, cycles, nowhere-zero flows, edge colorings
• English key words: graphs, cycles, nowhere-zero flows, edge colorings
• Academic year of topic announcement: 2013/2014
• Thesis type: diploma thesis
• Thesis language: angličtina
• Department: Computer Science Institute of Charles University (32-IUUK)
• Supervisor: doc. Mgr. Robert Šámal, Ph.D.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 03.07.2014
• Date of assignment: 10.07.2014
• Confirmed by Study dept. on: 18.07.2014
• Date and time of defence: 03.06.2015 09:00
• Date of electronic submission: 04.05.2015
• Date of submission of printed version: 05.05.2015
• Date of proceeded defence: 03.06.2015
• Opponents: RNDr. Edita Rollová, Ph.D.

Guidelines

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.

References

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