Structural Graph Theory and Applications

该研究计划旨在推进知识和解决两个广泛但相互关联的领域的开放问题：图论和理论计算机科学。我们的主要重点是组合学，代数，拓扑学和几何之间的相互作用，主要目标是将结果应用于高效算法的设计，获得下界，以及生产处理大型网络和大型数据集的工具。我们的目标是指导一个广泛的研究项目，并在每个拟议的领域做出重要贡献。******1)结构图论：(i)图的次要和浸入。我们的目标是用强大的新技术来攻击哈德维格猜想。还有许多其他的开放问题：关于图形沉浸的HC，沉浸的准排序，完全奇怪的沉浸和算法问题。交叉号码。我们有了令人鼓舞的新结果，这可能会导致一个关于交叉临界图的强大结构理论，并可能有几个算法后果。（iii）从有效算法和分类障碍的角度，对图嵌入到曲面、顶点图和眼三角洲可约性、无链接和无结嵌入以及二维复合体嵌入到二维复合体或三维流形中的阻碍进行分类。（iv）图嵌入的灵活性。我们将发展关于固定曲面上图嵌入结构的一般理论，并产生一个最终的概括，它将描述一般图嵌入的所有可能的灵活性。******2)代数图论。以前我们描述了用“小”分隔符的顶点传递图的粗略表征。我们将探讨这一结果的后果。我们的目标之一是增加我们对图同构问题的理解。第二个代数问题是关于图的特征值，我们计划获得具有有限个大特征值的图的结构的粗略表征。这些问题都与图的极限有关。******3)大图和图限。我们的目标是研究图在曲面和其他结构化图类上的极限。表面上的随机图可以用连续树（布朗图）来建模。我们将通过几何方法进一步了解这一领域。******4)图形着色。在此，我们将在最近工作的基础上，从三个方向开展工作。最近我们证明了1979年Erdos和Neumann-Lara关于二色数猜想的分数形式。我们的目标是解决整个猜想。我们还证明了1971年关于色多项式极值的托梅斯库猜想的4色情形。我们的目标是证明托梅斯库猜想的全面性。第三，我们计划找到一个四色平面图的线性时间算法，并解决几个突出的问题，如关于边着色次三次图的Grotzsch猜想，或Tutte的四流猜想。

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.