Forbidding Induced Subgraphs: Structure and Properties

禁止诱导子图：结构和性质

• 批准号: 1763817
• 负责人: Maria Chudnovsky
• 金额: $ 21万
• 依托单位: Princeton University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-07-01 至 2022-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1763817&HistoricalAwards=false
• 关键词: Forbidding; Induced; Subgraphs; Structure; Properties

The project aims to study a number of well-known open problems in graph theory, as well as new problems suggested by them. The proposed questions are all related to the study of graphs with certain forbidden substructures. The line of inquiry that guides the research is: what is the global difference between general graphs and graphs that do not contain a particular substructure? These problems have been open for a while, but the PI and her collaborators have recently made progress on most of them. It is only now that a global picture is coming to light, and it seems likely that methods used for some of the problems can carry over to others. Exploring this crossover of ideas will undoubtedly lead to the development of new methods and approaches that were too far out of reach before, and are likely to allow further exciting developments.The focus of the project is on the influence of excluding an induced subgraph (or a family of them) on the structure of a graph. Specifically the PI and her collaborators plan to explore the following aspects to this question: the connections between the clique number and the chromatic number, the complexity of the graph coloring problem, the structure of minimal obstructions to colorability, the presence in a graph of large tightly structured subgraphs (the Erdos-Hajnal conjecture and its variants), and more.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.

该项目旨在研究图论中一些著名的公开问题，以及由它们提出的新问题。所提出的问题都与具有某些禁止子结构的图的研究有关。指导这项研究的研究思路是：一般图形和不包含特定子结构的图形之间的总体差异是什么？这些问题已经解决了一段时间，但PI和她的合作者最近在大多数问题上取得了进展。直到现在，一幅全球图景才浮出水面，解决其中一些问题的方法似乎可能会延续到其他问题上。探索这种思想的交叉无疑将导致以前遥不可及的新方法和途径的发展，并可能允许进一步令人兴奋的发展。该项目的重点是排除一个诱导子图(或它们的一族)对图结构的影响。具体地说，PI和她的合作者计划探索这个问题的以下方面：集团数和色数之间的联系，图着色问题的复杂性，可着色性的最小障碍的结构，大型紧密结构子图(鄂尔多斯-哈杰纳尔猜想及其变种)图中的存在，以及更多。这个奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Detecting an Odd Hole

• DOI: 10.1145/3375720
• 发表时间: 2019-03
• 期刊: Journal of the ACM (JACM)
• 作者: M. Chudnovsky;A. Scott;P. Seymour;S. Spirkl

Induced subgraphs and tree decompositions I. Even-hole-free graphs of bounded degree

归纳子图和树分解 I. 有界度的偶孔无图

• DOI: 10.1016/j.jctb.2022.05.009
• 发表时间: 2022
• 期刊: Series B
• 作者: Abrishami, Tara;Chudnovsky, Maria;Vušković, Kristina
• 通讯作者: Vušković, Kristina

Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs

无H图中最大权独立集问题的拟多项式时间逼近方案

• DOI: 10.1137/1.9781611975994.139
• 发表时间: 2020
• 期刊: Proceedings of the annual ACMSIAM symposium on discrete algorithms
• 作者: Chudnovsky, Maria.;Pillipczuk, Marcin.;Pillipczuk, Mihal;and Thomasse, Stephan.
• 通讯作者: and Thomasse, Stephan.

Erdős-Hajnal for cap-free graphs

ErdÅs-Hajnal 用于无上限图

• DOI: 10.1016/j.jctb.2021.07.006
• 发表时间: 2021
• 期刊: Series B
• 作者: Chudnovsky, Maria;Seymour, Paul
• 通讯作者: Seymour, Paul

Induced equators in flag spheres

旗球中的感应赤道

• DOI: 10.1016/j.jcta.2020.105283
• 发表时间: 2020
• 期刊: Series A
• 作者: Chudnovsky, Maria;Nevo, Eran
• 通讯作者: Nevo, Eran