Disjoint Paths in Graphs and Coloring

Georgia Tech Research Corporation, Atlanta GA

Investigators

Abstract

Many real word problems concern large systems that may be modeled by graphs. Those systems include communication networks, social networks, and neural networks. To analyze those systems, it is important to understand the structure of the underlying graphs, in terms of the existence of certain structure, connectivity, and partitions. It is often the case that methods for studying graph structures lead to efficient algorithms. This project studies structure of graphs with certain forbidden substructures, as well as related problems on connectivity and coloring. This project also contains research problems that are suitable for students. Determining the chromatic number of an arbitrary graph is difficult. However, one might be able to obtain a reasonable bound on the chromatic numbers of graphs not containing a given structure, such as subdivisions of a graph. The PI will work on an old conjecture of Hajos: Graphs without K_5-subdivisions are 4-colorable. If true, this would be a generalization of the well known Four Color Theorem. The PI will study the structure of such graphs, as well as its connections to connectivity problems about disjoint paths in graphs, including a long standing conjecture of Lovasz on removable paths. 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.