Structural Graph Theory and Applications

结构图理论及应用

• 批准号: RGPIN-2018-05116
• 负责人: Mohar, Bojan
• 金额: $ 5.39万
• 依托单位: Simon Fraser University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2019
• 资助国家: 加拿大
• 起止时间: 2019-01-01 至 2020-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=691728
• 关键词: 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）图的子项和浸入。我们的目标是攻击Hadwiger猜想使用强大的新技术。还有大量的其他开放的问题：HC的图浸入，以及准排序的浸入，完全奇浸入，和算法问题。(ii)交叉号码。我们有令人鼓舞的新结果，这可能会导致一个强大的结构理论交叉临界图，并可能有几个算法的后果。(iii)从有效算法和障碍物分类的角度，将图的嵌入障碍物分类为曲面、顶点图和Y-delta约化、无链和无结嵌入以及2维复形在2-复形或3-流形中的嵌入。(iv)图形嵌入的灵活性。我们将发展关于图在固定曲面中嵌入结构的一般理论，并产生一个最终的推广，它将描述一般图嵌入的所有可能的灵活性。2)代数图论先前我们描述了具有“小”分隔符的点传递图的粗略刻画。我们将探讨这一结果的后果。我们的目标之一是增加我们对图同构问题的理解。第二个代数问题是关于图的特征值，在那里我们计划获得一个粗略的表征的结构图与有限数量的大特征值。这些问题与图形限制有关。* 3)大图和图极限。我们的目标是研究表面上的图和其他结构图类的限制。曲面上的随机图可以用连续树（布朗映射）来建模。我们将通过几何方法提供对这一领域的进一步理解。* 4)图着色在这里，我们将在我们最近工作的基础上，从三个方向开展工作。最近，我们证明了一个分数版本的1979年猜想的Erdos和Neumann-Lara的双色数。我们的目标是解决整个猜想。我们还证明了4色的情况下，1971年猜想Tomescu关于极值的色多项式。我们的目标是证明托梅斯库猜想在其充分的一般性。第三，我们计划找到一个4-着色平面图的线性时间算法，并解决几个悬而未决的问题，例如关于边着色次立方图的Grotzsch猜想，或Tutte的4-流猜想。