|
|
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
|
|
|
Minimal counterexamples to flow conjectures
Korcsok, Peter ; Šámal, Robert (advisor) ; Goodall, Andrew (referee)
We say that a~graph admits a~nowhere-zero k-flow if we can assign a~direction and a~positive integer (<k) as a~flow to each edge so that total in-flow into $v$ and total out-flow from $v$ are equal for each vertex $v$. In 1954, Tutte conjectured that every bridgeless graph admits a~nowhere-zero 5-flow and the conjecture is still open. Kochol in his recent papers introduces a~computational method how to prove that a~minimal counterexample cannot contain short circuits (up to length 10). In this Thesis, we provide a~comprehensive view on this method. Moreover, since Kochol does not share his implementation and in order to independently verify the method, we provide our source code that validates Kochol's results and extend them: we prove that any minimal counterexample to the conjecture does not contain any circuit of length less than 12. Powered by TCPDF (www.tcpdf.org)
|
|
|
Minimal counterexamples to flow conjectures
Korcsok, Peter ; Šámal, Robert (advisor) ; Goodall, Andrew (referee)
We say that a~graph admits a~nowhere-zero k-flow if we can assign a~direction and a~positive integer (<k) as a~flow to each edge so that total in-flow into $v$ and total out-flow from $v$ are equal for each vertex $v$. In 1954, Tutte conjectured that every bridgeless graph admits a~nowhere-zero 5-flow and the conjecture is still open. Kochol in his recent papers introduces a~computational method how to prove that a~minimal counterexample cannot contain short circuits (up to length 10). In this Thesis, we provide a~comprehensive view on this method. Moreover, since Kochol does not share his implementation and in order to independently verify the method, we provide our source code that validates Kochol's results and extend them: we prove that any minimal counterexample to the conjecture does not contain any circuit of length less than 12. Powered by TCPDF (www.tcpdf.org)
|
|
|
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 ::
