Seminar of Graph Theory - Mária Maceková (25.3.2021)
Thursday 25.3.2021 at 9:50
Mária Maceková (UPJŠ Košice):
Structure of edges in embedded graphs
MS TEAMS code (users from Comenius University in Bratislava): gglxxc7
Link (guests outside Comenius University in Bratislava)
Abstrakt:
The weight w(e) of an edge is the degree-sum of its end-vertices. In 1955, Kotzig proved that every 3-connected plane graph contains an edge of weight at most 13. Later, Borodin proved the existence of such an edge in plane graphs with minimum degree at least three. If we consider a graph embedded on a surface with non-positive Euler characteristic, minimum degree three and sufficiently large number of vertices, then the existence of an edge of weight at most 15 can be proved. In the talk we describe types of edges in connected graphs with minimum degree at least 2, minimum face size at least 3 and sufficiently large number of vertices embedded on a surface with non-positive Euler characteristic. We will also discuss the quality of our results.
Joint work with K. Cekanova and R. Sotak.
In this talk we present a brief overview of the classical results and explain the method, that allowed us to solve larger problems than traditional parallelization would allow. We have successfully used cyclic graph decompositions when solving systems with millions of variables.