N1-0218 Interplay of geometry, topology and algebra in structural and topological graph theory

FMF Logo Ang.jpg
imfm logo 198x120.png
ARRSLogo_2016_ang.png

Research project is (co) funded by the Slovenian Research Agency.

UL Member: Faculty of Mathematics and Physics

Code: N1-0218

Project: Interplay of geometry, topology and algebra in structural and topological graph theory

Period: 1. 4. 2022 - 31. 3. 2025

Range per year: 0,7 FTE category: C

Head: Bojan Mohar

Research activity: Natural sciences and mathematics

Research Organisations

Researchers

Citations for bibliographic records

Project description:

Hadwiger's Conjecture from 1943 claims that every graph with chromatic number k contains the complete graph of order k as a minor. This conjecture from structural graph theory is considered by many as the most outstanding problem in graph theory and its solution would have implications into the theory of algorithms. The conjectures of Hill and Turan from 1950's ask for the most "efficient" way of drawing complete graphs and complete bipartite graphs in the plane, meaning that we want to have the minimum possible number of crossings in such drawings. A third major open problem is the Graph Isomorphism Problem, whose (unknown) computational complexity plays a fundamental role in theoretical computing. These three fundamental questions in graph theory and theoretical computer science are long standing open problems that could be considered the long-term goals of the research agenda of the PI.

These problems have a very simple formulation but are far from being understood, despite many tools that have been developed to approach them. Progress in these problems and their variations have been using methods from geometry, topology, and algebra used in graph theory and algorithms. Although the problems look strikingly different, the methods to approach them have a lot in common. By studying graphs on surfaces, limits of graph drawings, random embeddings, algorithms for conjugacy in symmetric groups, and algebraic and topological bounds on the chromatic number and clique minors in graphs, it is hoped that the original, big problems will be much better understood and, hopefully, we will resolve some of them.