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
• 财政年份: 2018
• 资助国家: 加拿大
• 起止时间: 2018-01-01 至 2019-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=664636
• 关键词: 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 都有机会做出贡献。