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）交叉数字。我们有鼓励的新结果，这可能会导致有关跨越批判图的强大结构理论，并可能带来几种算法的后果。 （iii）将障碍物分类为图表的嵌入到表面，最高图和Wye-delta可降低性，无连锁和无结的嵌入以及2个复合物中的2维复合物的嵌入以及3个manifolds中的二维复合物的嵌入，均来自有效的算法和分类障碍物的观点。 （iv）图嵌入的灵活性。我们将开发有关固定表面中图的嵌入结构的一般理论，并产生最终的概括，以描述一般图嵌入的所有可能的灵活性。2）代数图理论。以前，我们描述了具有“小”分离器的顶点及物图的粗略表征。我们将探讨此结果的后果。我们的目标之一是提高我们对图形同构问题的理解。第二个代数问题是关于图特征值，我们计划在其中获得具有界数大量特征值的图形结构的粗略表征。这些问题与图形限制有联系。3）大图和图形限制。我们的目的是研究表面和其他结构图类别的图形限制。表面上的随机图可以通过连续树建模（布朗图）。我们将通过几何方法进一步了解该区域。4）图形着色。在这里，我们将以三个方向工作，以我们最近的工作为基础。最近，我们证明了1979年的Erdos和Neumann-Lara关于二分法数字的猜想的分数版本。我们的目标是解决全部猜想。我们还证明了1971年Tomescu关于色多项式的最大值的tomescu的4种案例。我们的目标是证明Tomescu的全部猜想。第三，我们计划找到一种用于4色平面图的线性时间算法，并攻击几个出色的问题，例如Grotzsch关于边彩下图形图或Tutte的4流构想的猜想。