Structural Graph Theory and Applications

结构图理论及应用

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