How do forbidden induced subgraphs impact global phenomena in graphs?

禁止诱导子图如何影响图中的全局现象？

• 批准号: RGPIN-2017-06673
• 负责人: Seamone, Benjamin
• 金额: $ 1.46万
• 依托单位: Université de Montréal
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=711490
• 关键词: How; do; forbidden; induced; subgraphs

My research program is in theoretical and algorithmic graph theory. I seek to better understand structural properties of graphs through the lens of parameters motivated by real world problems. A “graph” (or “network”) is a set of objects (“vertices”) and a set of pairs of vertices (“edges”). In most applications, graphs are used to represent a system of connections or relationships. The Facebook graph has users as its vertices and two users are connected by an edge if they are friends. A highway system can be modelled by a graph whose vertices are cities and towns, and the edges are roads and highways. A telecommunications network can be modelled by a graph where vertices are towers and two are connected by an edge if they can communicate with one another. Many problems we would like to solve in a graph theoretic setting are computationally very difficult. For example, suppose a delivery truck wishes to visit every city in a region exactly once in a single trip, finishing where it started. The time it takes to determine if such a route even exists grows extremely rapidly as the number of cities to consider increases. Under what conditions can we efficiently solve such a problem? Even better, what conditions necessarily imply a positive solution? My research program focuses on finding subgraphs which, when forbidden from occurring in a graph as an induced subgraph, guarantee a positive answer to a question which is otherwise difficult to solve. In the long term, I aim to deeply understand the effect of forbidding induced subgraphs on the following three aspects of a graph (examples of real world motivations for each aspect given in parentheses): (1) the existence of long cycles (efficient or optimal routing in networks), (2) covering the graph with particular subgraphs, especially complete graphs (optimizing computer performance, food webs, analysis of real world complex networks), and (3) the chromatic number of the graph, especially as it relates to other graph parameters (scheduling problems, channel assignment in communication networks). Over the next five years, I intend to make progress in all three themes. I am interested in generalizing known closure concepts in H-free graphs, a project that is large enough in scope to warrant support from both PhD students and postdoctoral fellows. These concepts are vital tools for guaranteeing spanning cycles in H-free graphs. Recent progress on edge clique coverings suggests new avenues to be explored regarding this parameter, including solving one remaining case of an open problem on covering the edges of claw-free graphs with cliques. Finally, I will pursue an open conjecture related to chi-boundedness which, surprisingly, relates induced subgraphs, paths and cycles, and graph colouring. Preliminary evidence suggests improvements can be made on the best known results related to the conjecture, and opportunities exist for contributions from HQPs of all levels.

我的研究项目是理论和算法图论。 我试图通过真实的世界问题所激发的参数的透镜来更好地理解图的结构特性。 “图”（或“网络”）是对象（“顶点”）的集合和顶点对（“边”）的集合。 在大多数应用中，图形用于表示连接或关系的系统。 Facebook图的顶点是用户，如果两个用户是朋友，则通过边连接。 高速公路系统可以用一个图来建模，该图的顶点是城镇，边是道路和高速公路。 电信网络可以用一个图来建模，其中顶点是塔，如果它们可以相互通信，则两个顶点通过边连接。 我们想在图论中解决的许多问题在计算上是非常困难的。 例如，假设一辆送货卡车希望在一次行程中访问一个地区的每个城市一次，并在它开始的地方完成。 随着需要考虑的城市数量的增加，确定这样一条路线是否存在所需的时间也会迅速增长。 在什么样的条件下，我们才能有效地解决这样的问题？ 更好的是，什么样的条件必然意味着正解？ 我的研究计划的重点是寻找子图，当禁止发生在一个图作为一个诱导子图，保证一个肯定的答案，否则很难解决的问题。 从长远来看，我的目标是深入理解禁止诱导子图对图的以下三个方面的影响（括号中给出了每个方面的真实的动机示例）： (1)长周期的存在（网络中的有效或最佳路由）， (2)用特定的子图，特别是完全图（优化计算机性能，食物网，分析真实的世界复杂网络）覆盖图，以及 (3)图的色数，特别是当它与其他图参数（调度问题，通信网络中的信道分配）有关时。 在今后五年中，我打算在所有三个主题上取得进展。 我感兴趣的是推广已知的闭包概念在H-自由图，一个项目，这是足够大的范围，以保证支持博士生和博士后研究员。 这些概念是保证无H图生成圈的重要工具。 边缘集团覆盖的最新进展提出了新的途径来探索关于这个参数，包括解决一个悬而未决的问题，覆盖无爪图的边缘与集团的一个剩余的情况。 最后，我将追求一个开放的猜想有关的卡有界性，令人惊讶的是，涉及诱导子图，路径和周期，图着色。 初步证据表明，可以对与猜想相关的最知名的结果进行改进，并且存在来自所有级别的HQP的贡献的机会。