Structural Graph Theory and Applications

结构图理论及应用

• 批准号: RGPIN-2018-05116
• 负责人: Mohar, Bojan
• 金额: $ 5.39万
• 依托单位: Simon Fraser University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2018
• 资助国家: 加拿大
• 起止时间: 2018-01-01 至 2019-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=659997
• 关键词: Structural; Graph; Theory; 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.

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