Coloring Graphs with Forbidden Structures and Investigations Related to Ramsey Theory

点击翻译按钮获取中文摘要

This research project aims to investigate a variety of fundamental problems in the areas of structural graph theory and extremal combinatorics. Often such problems are related to other areas including theoretical computer science, geometry, information theory, harmonic analysis and number theory. Progress on these problems will advance our understanding of related aspects of graph theory and combinatorics. The PI and her collaborators have recently made progress on most of them. It is expected that further work on these problems will lead to new methods and applications. Graduate and undergraduate students will be trained during this award.The project investigates problems related to the well-known Hadwiger's Conjecture, the Erdös-Lovász Tihany Conjecture and Ramsey related problems. The PI and her collaborators have recently made the first asymptotic improvement since 1980s on the chromatic number of graphs with no clique minor of order k using new techniques. In this proposal, the PI and her collaborators plan to explore the following problems: Linear Hadwiger’s Conjecture for graphs of small order; the minimal counterexamples to Hadwiger’s Conjecture for graphs with independence number two by working on the Füredi-Gyárfás-Simonyi Conjecture; Hadwiger’s Conjecture and the Erdös-Lovász Tihany Conjecture for special family of graphs; establishing tight bounds on the minimum number of edges of co-critical graphs; and finding graphs such that its list Ramsey number is the same as its classical Ramsey number. Progress on these problems will likely lead to the development of new methods and approaches that were too far out of reach before and are expected to allow further exciting developments.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.