Structure of Group-Labeled Graphs and Digraphs

Graphs serve as mathematical models for various kinds of networks consisting of nodes and edges that connect pairs of nodes. Edges in networks often carry additional data, such as distances, costs, or labels describing relationships between nodes. In these settings, fundamental problems involve finding paths, cycles, and other structures whose combined edge data satisfy prescribed constraints. Group-labeled graphs provide a unified framework for expressing many such constraints. This project aims to develop a structural theory of group-labeled graphs that yields general tools and efficient algorithms for a wide range of problems involving constrained substructures in graph theory and computer science. The PI will train graduate students as part of this project. This project will investigate the structure of group-labeled graphs excluding a fixed group-labeled graph as a minor, as well as characterizations of the Erdos-Posa property and the half-integral Erdos-Posa property of constrained paths, cycles, and group-labeled minors and subdivisions. These results will enable the design of efficient algorithms for group-labeled graphs. This project will also investigate group-labeled directed graphs, with the goal of establishing a new framework that connects and extends existing structural and algorithmic results on constrained directed paths and cycles. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.