| Meno: | Dávid
|
|---|
| Priezvisko: | Miąiak
|
|---|
| Názov: | Flow polynomials of k-poles
|
|---|
| Vedúci: | doc. RNDr. Robert Luko»ka, PhD.
|
|---|
| Rok: | 2024
|
|---|
| Kµúčové slová: | multipole, flow polynomial, planar graph, Four color theorem
|
|---|
| Abstrakt: | The Four color theorem can be reformulated as the problem of finding flows over the group (Z2xZ2, +) in cubic planar graphs. Using the recursive relation for the flow polynomial, it is possible to express the number of flows in a multipole (a graph with dangling edges) as a linear combination of flow counts in small, basic multipoles. In this thesis, we study the properties of planar multipoles from the perspective of the coefficients in this expression. We focus on multipole connectivity and the number of flows with given boundary values; these properties are closely related to the Four color theorem. We also present an algorithm for computing the coefficients and the results of computations on cubic planar multipoles up to approximately 30 vertices. Based on these results, we observe and formulate a hypothesis about 3-edge-colorings of cubic planar 5-poles: At least one-quarter of all colorings of each 5-pole contain three consecutive dangling edges of the same color. Finally, we investigate the properties of a potential counterexample to this hypothesis.
|
|---|