Algebraic and Topological Methods in Graph Theory

该研究项目旨在促进两个广泛但相互关联的领域的知识和解决公开问题：图论和理论计算机科学。我们的主要重点是组合学、代数、拓扑学和几何学之间的相互作用，主要目标是将结果应用于高效算法的设计、获得下界和产生处理大型网络和大型数据集的工具。以下列出了主要的研究方向。 1)拓扑图和结构图论：研究图在曲面中嵌入的灵活性、交叉数、拓扑嵌入的算法和障碍、图的子式和图的浸没。 2)代数图论：研究顶点传递图，目的是增加我们对图同构问题、图和有向图的特征值的理解。 3)大图和图的极限：利用几何方法(圆填充、曲率)和结构图之间的Gromov-Haudorff距离的一种形式，对稀疏图和曲面上的图或次闭族中的图的极限。 4)图和有向图染色：Hadwiger猜想及其推广，Erdos-Hajal猜想和Caccetta-Haggkvist猜想。

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.