How do forbidden induced subgraphs impact global phenomena in graphs?

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

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.