Topological Minors, Connectivity, and Partitions

Georgia Tech Research Corporation, Atlanta GA

Investigators

Abstract

Many important systems in science and engineering, including wireless communications, complex networks such as the Internet, and neural science, have natural formulations in terms of graphs. To analyze such systems, it is important to understand the structure of the associated classes of graphs and to decompose those graphs into structured pieces. Such structural information and decomposition can then be used to provide good solutions to problems formulated in these models. This research project investigates problems concerning structure and decomposition of certain fundamental classes of graphs. Research materials arising from the project will be used to train undergraduate, graduate, and early-career researchers in this field of research. Using structural and extremal techniques, the investigator and collaborators have recently resolved a longstanding conjecture on graphs containing no topological K5 and several conjectures on partitions of graphs and hypergraphs. This project extends this research to study related problems, including conjectures concerning non-separating paths and several problems concerning judicious partitions of graphs and hypergraphs.