Graph Decompositions and Their Applications

Texas A&M University, College Station TX

Investigators

Abstract

Graph theory is a central research direction in combinatorics. Graphs are abstract mathematical objects that have been extensively used to model problems in different subjects, such as in network theory, integrated circuit design, and scheduling theory. A general approach for solving problems on complicated graphs is to first decompose the original graph into more tractable pieces, solve the problems on those pieces, and finally construct the answer for the original graph from the answers for those smaller pieces. Different problems require different decomposition techniques and many decomposition theorems have been developed and successfully applied to solve long standing conjectures. However, it is unclear whether those developed decomposition theorems are sufficient to solve other open problems. The purpose of this project is to address this fundamental issue by developing new structure decomposition theorems to enrich the toolkit and applying them and other developed theorems to solve major conjectures in graph theory and theoretical computer science. This project includes many research problems that are suitable for graduate students and advanced undergraduate students. Progress made on this project will advance knowledge in mathematics and contribute to education. The aim of this project is to prove new decomposition theorems and apply them to solve open problems in graph theory and computer science. An objective is to prove a global tree-like decomposition theorem for graphs in immersion-closed families and apply it to solve an open problem related to a conjecture of Abu-Khzam, Langston, Lescure and Meyniel on graph coloring. In addition, a recent newly developed notion for layered tree-decomposition will be considered in order to generalize algorithmic results on minor-closed families to strictly wider classes of graphs, such as graphs embeddable in a fixed surface with some crossings allowed. Another objective of this project is to solve a conjecture of Dvorak and Norin on island decomposition which is motivated by a strengthening of a relaxation of Hadwiger’s conjecture on coloring graphs in minor-closed families. The strategy for attacking the above problems is to further investigate the structure of graphs, where new ideas will be involved, and the PI's earlier results and other structure theorems in the literature will be exploited. 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.