How do forbidden induced subgraphs impact global phenomena in graphs?

点击翻译按钮获取中文摘要

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.