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
• 财政年份: 2019
• 资助国家: 加拿大
• 起止时间: 2019-01-01 至 2020-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=677175
• 关键词: 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图中生成循环的重要工具。关于边缘团覆盖的最新进展提出了关于该参数的新探索途径，包括解决关于用团覆盖无爪图边缘的开放问题的一个剩余情况。最后，我将追求一个与chi-bounded有关的开放猜想，令人惊讶的是，它与诱导子图、路径和循环以及图着色有关。初步证据表明，可以对与该猜想有关的最著名的结果进行改进，并且存在各级HQPs贡献的机会。