Structure and Coloring of Sparse Graphs
稀疏图的结构和着色
基本信息
- 批准号:RGPIN-2022-03246
- 负责人:
- 金额:$ 2.26万
- 依托单位:
- 依托单位国家:加拿大
- 项目类别:Discovery Grants Program - Individual
- 财政年份:2022
- 资助国家:加拿大
- 起止时间:2022-01-01 至 2023-12-31
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
The PI proposes to continue his investigation of interplay between extremal, structural and coloring properties of sparse graphs, focusing on minor-closed graph classes. Graph minor theory is a deep and rich area of graph theory, initially developed by Robertson and Seymour in a series of twenty three papers. It continues to be an active area of research with extensive algorithmic applications. Some of the methods developed as part of the theory have been successfully used in practical computations. One of the central results in graph minor theory is the graph structure theorem of Robertson and Seymour, which gives an approximate structural description of graphs that do not contain a fixed graph as a minor. The PI proposes to continue his ongoing long term project, started jointly with Robin Thomas, the goal of which is a refinement of many aspects of this theory. In particular, one of the goals of the project is to obtain bounds on connectivity which guarantees existence of certain minors and related configurations (linkages, topological minors, etc.) in graphs of given size. Luke Postle and the PI recently obtained effective bounds of the type mentioned above, which allowed them to make progress towards Hadwiger's conjecture, a longstanding question, which greatly strengthens the Four Color Theorem. This conjecture is possibly the most famous open problem in graph theory, and the PI proposes to continue sharpening the tools which allowed recent progress in search for further breakthroughs. Finally, The PI also proposes to continue investigation of extremal aspects of graph minor theory and the development of a suite of generic tools for problems in this area.
PI建议继续研究稀疏图的极值,结构和着色属性之间的相互作用,重点是小闭图类。图子式理论是图论中一个很深很丰富的领域,最初由Robertson和Seymour在23篇论文中发展起来。它仍然是一个活跃的研究领域,具有广泛的算法应用。作为理论的一部分而开发的一些方法已成功地用于实际计算。图子理论中的一个中心结果是Robertson和Seymour的图结构定理,它给出了不包含固定图作为子图的图的近似结构描述。PI建议继续他正在进行的长期项目,与罗宾托马斯共同开始,其目标是细化这一理论的许多方面。特别地,该项目的目标之一是获得连通性的界限,该界限保证某些未成年人和相关配置(链接,拓扑未成年人等)的存在。在给定大小的图中。Luke Postle和PI最近获得了上述类型的有效界,这使他们能够在Hadwiger猜想方面取得进展,这是一个长期存在的问题,大大加强了四色定理。这个猜想可能是图论中最著名的开放问题,PI建议继续锐化工具,以便在寻找进一步突破方面取得最新进展。最后,PI还建议继续研究图子理论的极值方面,并为这一领域的问题开发一套通用工具。
项目成果
期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
数据更新时间:{{ journalArticles.updateTime }}
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
Norin, Sergey其他文献
The Spectrum of Triangle-Free Graphs
无三角形图的谱
- DOI:
10.1137/22m150767x - 发表时间:
2023 - 期刊:
- 影响因子:0.8
- 作者:
Balogh, József;Clemen, Felix Christian;Lidický, Bernard;Norin, Sergey;Volec, Jan - 通讯作者:
Volec, Jan
Counterexamples to a Conjecture of Harris on Hall Ratio
哈里斯霍尔比猜想的反例
- DOI:
10.1137/18m1229420 - 发表时间:
2022 - 期刊:
- 影响因子:0.8
- 作者:
Blumenthal, Adam;Lidický, Bernard;Martin, Ryan R.;Norin, Sergey;Pfender, Florian;Volec, Jan - 通讯作者:
Volec, Jan
Norin, Sergey的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Norin, Sergey', 18)}}的其他基金
Extremal and Structural Aspects of Graph Minor Theory
图小论的极值和结构方面
- 批准号:
RGPIN-2017-05010 - 财政年份:2021
- 资助金额:
$ 2.26万 - 项目类别:
Discovery Grants Program - Individual
Extremal and Structural Aspects of Graph Minor Theory
图小论的极值和结构方面
- 批准号:
RGPIN-2017-05010 - 财政年份:2020
- 资助金额:
$ 2.26万 - 项目类别:
Discovery Grants Program - Individual
Extremal and Structural Aspects of Graph Minor Theory
图小论的极值和结构方面
- 批准号:
RGPIN-2017-05010 - 财政年份:2019
- 资助金额:
$ 2.26万 - 项目类别:
Discovery Grants Program - Individual
Extremal and Structural Aspects of Graph Minor Theory
图小论的极值和结构方面
- 批准号:
RGPIN-2017-05010 - 财政年份:2018
- 资助金额:
$ 2.26万 - 项目类别:
Discovery Grants Program - Individual
Extremal and Structural Aspects of Graph Minor Theory
图小论的极值和结构方面
- 批准号:
RGPIN-2017-05010 - 财政年份:2017
- 资助金额:
$ 2.26万 - 项目类别:
Discovery Grants Program - Individual
Semi-definite method in Combinatorics
组合学中的半定法
- 批准号:
418520-2012 - 财政年份:2016
- 资助金额:
$ 2.26万 - 项目类别:
Discovery Grants Program - Individual
Semi-definite method in Combinatorics
组合学中的半定法
- 批准号:
418520-2012 - 财政年份:2015
- 资助金额:
$ 2.26万 - 项目类别:
Discovery Grants Program - Individual
Semi-definite method in Combinatorics
组合学中的半定法
- 批准号:
418520-2012 - 财政年份:2014
- 资助金额:
$ 2.26万 - 项目类别:
Discovery Grants Program - Individual
Semi-definite method in Combinatorics
组合学中的半定法
- 批准号:
418520-2012 - 财政年份:2013
- 资助金额:
$ 2.26万 - 项目类别:
Discovery Grants Program - Individual
Semi-definite method in Combinatorics
组合学中的半定法
- 批准号:
418520-2012 - 财政年份:2012
- 资助金额:
$ 2.26万 - 项目类别:
Discovery Grants Program - Individual
相似海外基金
Research on Graph Coloring and Graph Structure
图着色与图结构研究
- 批准号:
2348702 - 财政年份:2024
- 资助金额:
$ 2.26万 - 项目类别:
Standard Grant
Forbidding Induced Subgraphs: Decompositions, Coloring and Algorithms
禁止诱导子图:分解、着色和算法
- 批准号:
2348219 - 财政年份:2024
- 资助金额:
$ 2.26万 - 项目类别:
Continuing Grant
Research on Coloring Materials and Painting Expressions of Painters in Wakayama in the Edo Period
江户时代和歌山画家的色彩材料与绘画表现研究
- 批准号:
23H00586 - 财政年份:2023
- 资助金额:
$ 2.26万 - 项目类别:
Grant-in-Aid for Scientific Research (B)
Coloring Graphs with Forbidden Structures and Investigations Related to Ramsey Theory
具有禁止结构的着色图以及与拉姆齐理论相关的研究
- 批准号:
2153945 - 财政年份:2022
- 资助金额:
$ 2.26万 - 项目类别:
Standard Grant
Online Coloring with a Bounded Palette
使用有限调色板在线着色
- 批准号:
575050-2022 - 财政年份:2022
- 资助金额:
$ 2.26万 - 项目类别:
University Undergraduate Student Research Awards
Vivid laser coloring by nitridation and surface periodic structure formation
通过氮化和表面周期性结构形成实现生动的激光着色
- 批准号:
22K03845 - 财政年份:2022
- 资助金额:
$ 2.26万 - 项目类别:
Grant-in-Aid for Scientific Research (C)
The Road Coloring Problem and the O(G) Conjecture
道路着色问题和 O(G) 猜想
- 批准号:
574185-2022 - 财政年份:2022
- 资助金额:
$ 2.26万 - 项目类别:
University Undergraduate Student Research Awards
Development of clinical test using new amino acid coloring method
新氨基酸显色法临床试验的开发
- 批准号:
21K07394 - 财政年份:2021
- 资助金额:
$ 2.26万 - 项目类别:
Grant-in-Aid for Scientific Research (C)