Structural Graph Theory and Applications

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

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. Our aim is to direct a broad research program and make essential contributions in each of the proposed areas.1) Structural graph theory: (i) Graph minors and immersions. Our aim is to attack Hadwiger's conjecture using powerful new techniques. There is abundance of other open problems: HC for graph immersions, well quasi-ordering of immersion, totally odd immersions, and algorithmic questions. (ii) Crossing numbers. We have encouraging new results, which may lead to a powerful structure theory about crossing critical graphs and may have several algorithmic consequences. (iii) Classifying obstructions to embeddings of graphs into surfaces, apex graphs and wye-delta reducibility, linkless and knotless embeddings and embeddings of 2-dimensional complexes in 2-complexes or in 3-manifolds, both from the viewpoint of efficient algorithms and classifying obstructions. (iv) Flexibility of graph embeddings. We will develop general theory about the structure of embeddings of graphs in a fixed surface and produce an ultimate generalization that would describe all possible flexibilities of general graph embeddings.2) Algebraic graph theory. Previously we described rough characterization of vertex transitive graphs with "small" separators. We will explore the consequences of this result. One of our goals is to increase our understanding of the graph isomorphism problem. The second algebraic question is about graph eigenvalues, where we plan to obtain a rough characterization of the structure of graphs with a bounded number of large eigenvalues. These questions have ties to graph limits.3) Large graphs and graph limits. Our aim is to study limits of graphs on surfaces and other structured graph classes. Random graphs on a surface can be modeled by continuous trees (Brownian map). We will provide further understanding of this area via geometric methods.4) Graph coloring. Here we will work in three directions, building on our recent work. Recently we proved a fractional version of a 1979 conjecture of Erdos and Neumann-Lara about the dichromatic number. Our goal is to resolve the full conjecture. We also proved the 4-chromatic case of a 1971 conjecture of Tomescu about extremal values of chromatic polynomials. Our goal is to prove Tomescu conjecture in its full generality. Thirdly, we plan to find a linear-time algorithm for 4-coloring planar graphs and attack several outstanding questions, e.g. the Grotzsch conjecture about edge-coloring subcubic graphs, or the 4-flow conjecture of Tutte.