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和她的合作者计划探索以下方面的问题：集团数量和色数之间的联系，图形着色问题的复杂性，最小障碍物对可着色性的结构，在大型结构结构紧密结构的子图中存在的存在（Erdos-Hajnal的概念及其变种），以及该措施的范围，既有措施）。通过使用基金会的智力优点和更广泛影响的评论标准进行评估。

项目成果

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

Graphs with polynomially many minimal separators

具有多项式多个最小分隔符的图

• DOI: 10.1016/j.jctb.2021.10.003
• 发表时间: 2022
• 期刊: Series B
• 作者: Abrishami, Tara;Chudnovsky, Maria;Dibek, Cemil;Thomassé, Stéphan;Trotignon, Nicolas;Vušković, Kristina
• 通讯作者: Vušković, Kristina