|
|
Petersen coloring and variants
Bílková, Hana ; Šámal, Robert (advisor) ; Dvořák, Zdeněk (referee)
The Petersen coloring of 3-regular graph G is equivalent to the normal coloring by five colors. The normal coloring is a good coloring of edges such that every edge and its four neighbours have together three or five different colors. Jaeger conjectures that every bridgeless 3-regular graph has a Petersen coloring. If the conjecture were true, it would imply other interesting statements about 3-regular graphs. In this text we investigate normal coloring by more than five colors. Jaeger theorem about nowhere-zero Z2 3 -flow implies that every bridgeless graph has normal coloring by seven colors. Independently on the Jaeger theorem, we prove the existence of normal coloring by nine colors for graphs with a bridge, a cut of size two or with a triangle. The idea of our proof comes from Andersen's proof of existence of strong coloring by ten colors for 3-regular graphs. Finally, we sketch the idea of the proof for other classes of 3-regular graphs. 1
|
|
|
Variants of Petersen coloring for some graph classes
Bílková, Hana ; Šámal, Robert (advisor) ; Rollová, Edita (referee)
Normal coloring - an equivalent version of Petersen coloring - is a special proper 5-edge-coloring of cubic graphs. Every edge in a normally colored graph is normal, i.e. it uses together with its four neighbours either only three colors or all five colors. Jaeger conjectured that every bridgeless cubic graph has a normal coloring. This conjecture, if true, imply for example Cycle double cover conjecture. Here we solve a weakened version of Jaeger's problem. We are looking for a proper 5-edge-coloring such that at least a part of the edges is normal. We show a coloring of generalized prisms with two thirds of the edges normal and a coloring of graphs without short cycles with almost half of the edges normal. Then we propose a new approach to normal coloring - chains. We use chains to prove that there cannot be only one single mistake in an almost normally colored graph. We also prove some statements about cuts in a normally colored graph which also follow from nowhere-zero Petersen flow. Finally, we examine a four-cycle in a normally colored graph. 1
|
|
|
Petersen coloring and variants
Bílková, Hana ; Šámal, Robert (advisor) ; Dvořák, Zdeněk (referee)
The Petersen coloring of 3-regular graph G is equivalent to the normal coloring by five colors. The normal coloring is a good coloring of edges such that every edge and its four neighbours have together three or five different colors. Jaeger conjectures that every bridgeless 3-regular graph has a Petersen coloring. If the conjecture were true, it would imply other interesting statements about 3-regular graphs. In this text we investigate normal coloring by more than five colors. Jaeger theorem about nowhere-zero Z2 3 -flow implies that every bridgeless graph has normal coloring by seven colors. Independently on the Jaeger theorem, we prove the existence of normal coloring by nine colors for graphs with a bridge, a cut of size two or with a triangle. The idea of our proof comes from Andersen's proof of existence of strong coloring by ten colors for 3-regular graphs. Finally, we sketch the idea of the proof for other classes of 3-regular graphs. 1
|
guest ::
