Meno:  Dávid


Priezvisko:  Miąiak


Názov:  Flow polynomials of kpoles


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 3edgecolorings of cubic planar 5poles: At least onequarter of all colorings of each 5pole contain three consecutive dangling edges of the same color. Finally, we investigate the properties of a potential counterexample to this hypothesis.

