Graph structures and applications

Georgia Tech Research Corporation, Atlanta GA

Investigators

Abstract

Solutions to many problems in graph theory and extremal combinatorics require structural information of graphs and hypergraphs. The PI plans to study graph structures and their potential applications to graph colorings, in particular, a long standing conjecture of Seymour on topological K5. He also plans to work on several problems of Bollobas and Scott about partitions of graphs and hypergraphs. The PI has previously obtained a number of results in the proposed area using structural and extremal methods, and he plans to continue his work. Graph theory studies discrete structures such as networks (e.g., the Internet). Many problems in the real world may be formulated as problems on graphs, and mathematical techniques have been applied to attack such problems. When the structure of a class of graphs is well understood, efficient methods can often be found to solve problems on these graphs. When the structure is not clear, one often tries other mathematical methods (e.g. algebraic and probabilistic methods). This proposal considers both structural and extremal problems in graph theory. Progress on these problems should increase our understanding of graph theory and has potential applications to areas such as optimization and computer science.