Coloring Graphs with Forbidden Structures and Investigations Related to Ramsey Theory

本研究计划旨在探讨结构图论和极值组合学领域的各种基本问题。通常这些问题与其他领域有关，包括理论计算机科学、几何、信息论、谐波分析和数论。这些问题的进展将促进我们对图论和组合学相关方面的理解。PI和她的合作者最近在其中的大多数方面取得了进展。预计对这些问题的进一步研究将带来新的方法和应用。研究生和本科生将在此期间接受培训。该项目研究的问题与著名的哈维格猜想，Erdös-Lovász蒂哈尼猜想和拉姆齐相关的问题。PI和她的合作者最近使用新技术对没有k阶小团的图的色数进行了自20世纪80年代以来的第一次渐近改进。在这个提案中，PI和她的合作者计划探索以下问题：小阶图的线性Hadwiger猜想；对于独立性为2的图的最小反例，通过研究Füredi-Gyárfás-Simonyi猜想；特殊图族的Hadwiger猜想与Erdös-Lovász Tihany猜想在共临界图的最小边数上建立紧界并找到使其列表拉姆齐数与经典拉姆齐数相同的图。在这些问题上的进展可能会导致新的方法和途径的发展，这些方法和途径在以前是遥不可及的，并有望实现进一步令人兴奋的发展。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.