Research on Graph Coloring and Graph Structure

Georgia Tech Research Corporation, Atlanta GA

Investigators

Abstract

This research project studies the existence of certain configurations in graphs, as well as connections between those configurations and global properties of graphs. A well-known example is the Four-Color Theorem, which states that if a graph does not contain two specific configurations, then it is planar, and its vertices can be partitioned into at most four sets with no edges within each set. This project seeks similar results for other configurations, as well as sufficient conditions that guarantee the existence of certain configurations (such as cycles and matchings) in graphs. This project also contains research problems related to cycles in graphs and matchings in hypergraphs that are suitable for graduate students. This research project investigates two problems on graph coloring and graph structure. Hajos conjectured that graphs containing no subdivision of the 5-vertex complete graph are 4-colorable, which would generalize the Four-Color Theorem. Prior work on this conjecture led to the substantial understanding of the structure of those graphs, as well as its connections to several important problems concerning graph structures, including Lovasz's conjecture on non-separating paths and Thomassen's conjecture on 3-linked graphs. Another problem involves bounding the chromatic number of graphs not containing a given tree as an induced subgraph. Special trees will be considered to gain insight into this problem. 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.