Algebraic and Topological Methods in Graph Theory

点击翻译按钮获取中文摘要

The research program aims to advance knowledge and solve open problems in two broad but interrelated areas: graph theory and theoretical computer science. Our main emphasis is on interplay between combinatorics, algebra, topology and geometry with the main goal to apply the results in the design of efficient algorithms, obtaining lower bounds, and producing tools to handle large networks and large data sets. The following list outlines main research directions. 1) Topological and structural graph theory: Study of flexibility of embeddings of graphs in surfaces, crossing numbers, algorithms and obstructions for topological embeddings, graph minors, and immersions of graphs. 2) Algebraic graph theory: Study of vertex transitive graphs with aim to increase our understanding of the graph isomorphism problem, eigenvalues of graphs and digraphs. 3) Large graphs and graph limits: Limits of sparse graphs and graphs on surfaces or graphs in minor closed families, using approach via geometric methods (circle packing, curvature) and a version of Gromov-Haudorff distance between structured graphs. 4) Graph and digraph coloring: Hadwiger's conjecture and its generalizations, the Erdos-Hajnal Conjecture and the Caccetta-Haggkvist Conjecture.