Topological Minors of Graphs

图的拓扑未成年人

基本信息

  • 批准号:
    9700623
  • 负责人:
  • 金额:
    $ 5.19万
  • 依托单位:
  • 依托单位国家:
    美国
  • 项目类别:
    Standard Grant
  • 财政年份:
    1997
  • 资助国家:
    美国
  • 起止时间:
    1997-07-15 至 2000-06-30
  • 项目状态:
    已结题

项目摘要

Ding 9700623 This award provides funds for an investigation of three fundamental problems involving topological minors. The first problem is Robertson's double-path conjecture, which states that if a class G of graphs is closed under topological minors and is free of arbitrarily long double-paths, then G does not contain infinite antichains with respect t o the topological-minor relation. This is a fundamental conjecture in graph theory. It relates structural graph theory, combinatorial optimization, and classical combinatorics. The PI has made significant progress towards solving this conjecture, which includes, but is not limited to, proving the conjecture for all minor-closed classes of graphs and for the class of graphs of cutwidth at most three. He hopes that his past experience on this problem together with some of his new ideas will help him to settle this conjecture completely. The second problem is the edge version of Hajos' conjecture. Recently, the PI has established the edge version of Hadwiger's conjecture by identifying all minor- minimal graphs with chromatic index greater than n. Now he proposes to study topological-minor-minimal graphs with chromatic index greater than n. This is exactly the edge version of Hajos' conjecture, which claims that K_n is the only topological-minor-minimal graph with chromatic number greater than n. This problem relates not only to Hajos' conjecture and Hadwiger's conjecture, but also to Vizing's planar graph conjecture and several well-known results in this field. The third problem concerns unavoidable graphs of large crossing number. Crossing number is a typical graph parameter that is monotone with respect to the topological-minor relation but not with respect to the minor relation. A natural problem concerning this parameter is to understand what makes the crossing number big. One obvious cause is a high genus for the graph. There are also other causes. For example, for some large n, the containment of a topological minor D_ n can make the crossing number large. The PI proposes to characterize the complete list of unavoidable graphs of large crossing number. This research is in the general area of Combinatorics. One of the goals of Combinatorics is to find efficient methods of studying how discrete collections of objects can be arranged. The behavior of discrete systems is extremely important to modern communications. For example, the design of large networks, such as those occurring in telephone systems, and the design of algorithms in computer science deal with discrete sets of objects, and this makes use of combinatorial research.
丁9700623该奖项提供经费,用于研究涉及拓扑学未成年人的三个基本问题。第一个问题是Robertson的双路猜想,它指出如果一类图G在拓扑子集下是闭的,并且没有任意长的双路,则G不包含关于拓扑子集关系的无限反链。这是图论中的一个基本猜想。它将结构图论、组合优化和经典组合学联系在一起。PI已经在解决这一猜想方面取得了重大进展,包括但不限于证明了所有次闭图类和最多三个割宽的图类的猜想。他希望他过去在这个问题上的经验和他的一些新想法将帮助他完全解决这个猜想。第二个问题是Hajos猜想的边缘版本。最近,PI通过确定所有色指数大于n的次极小图建立了Hadwiger猜想的边版本。现在他建议研究色指数大于n的拓扑次极小图。这正是Hajos猜想的边版本,该猜想声称K_n是唯一的色数大于n的拓扑次极小图。这个问题不仅与Hajos猜想和Hadwiger猜想有关,还与Viving的平面图猜想和该领域的几个著名结果有关。第三个问题涉及不可避免的大交叉数的图。交叉数是一个典型的图参数,它对于拓扑-次关系是单调的,而对于次关系不是单调的。关于这个参数的一个自然问题是理解是什么使交叉数很大。一个明显的原因是图表的高亏格。还有其他原因。例如,对于某个较大的n,拓扑子式D_n的包含可以使交叉数变大。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 }}

Guoli Ding其他文献

Strengthened chain theorems for different versions of 4-connectivity
  • DOI:
    10.1016/j.disc.2022.113129
  • 发表时间:
    2023
  • 期刊:
  • 影响因子:
  • 作者:
    Guoli Ding;Chengfu Qin
  • 通讯作者:
    Chengfu Qin
A chain theorem for 4-connected graphs
  • DOI:
    10.1016/j.jctb.2018.07.005
  • 发表时间:
    2019-01-01
  • 期刊:
  • 影响因子:
  • 作者:
    Chengfu Qin;Guoli Ding
  • 通讯作者:
    Guoli Ding
Stable sets versus independent sets
稳定集与独立集
  • DOI:
  • 发表时间:
    1993
  • 期刊:
  • 影响因子:
    0.8
  • 作者:
    Guoli Ding
  • 通讯作者:
    Guoli Ding
Graphs without large $K_{2,n}$-minors
没有大$K_{2,n}$-次要的图
  • DOI:
  • 发表时间:
    2017
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Guoli Ding
  • 通讯作者:
    Guoli Ding
Minimal k-Connected Non-Hamiltonian Graphs
最小 k 连接非哈密顿图
  • DOI:
    10.1007/s00373-018-1874-z
  • 发表时间:
    2018
  • 期刊:
  • 影响因子:
    0.7
  • 作者:
    Guoli Ding;E. Marshall
  • 通讯作者:
    E. Marshall

Guoli Ding的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('Guoli Ding', 18)}}的其他基金

On structures of large graphs
关于大图的结构
  • 批准号:
    1500699
  • 财政年份:
    2015
  • 资助金额:
    $ 5.19万
  • 项目类别:
    Continuing Grant
Some problems in topological graph theory
拓扑图论的几个问题
  • 批准号:
    1001230
  • 财政年份:
    2010
  • 资助金额:
    $ 5.19万
  • 项目类别:
    Standard Grant
Minmax relations for graphs
图的最小最大关系
  • 批准号:
    0556091
  • 财政年份:
    2006
  • 资助金额:
    $ 5.19万
  • 项目类别:
    Standard Grant
Connectivity and Minors in Graph Theory
图论中的连通性和辅修
  • 批准号:
    9970329
  • 财政年份:
    1999
  • 资助金额:
    $ 5.19万
  • 项目类别:
    Standard Grant
Infinite Antichains of Graphs
图的无限反链
  • 批准号:
    9400946
  • 财政年份:
    1994
  • 资助金额:
    $ 5.19万
  • 项目类别:
    Standard Grant

相似海外基金

Minors at large
未成年人在逃
  • 批准号:
    EP/Y004302/1
  • 财政年份:
    2024
  • 资助金额:
    $ 5.19万
  • 项目类别:
    Research Grant
Implementation and impact of the ban on the sale of ultra-processed foods to minors in Mexico
墨西哥向未成年人销售超加工食品禁令的实施及影响
  • 批准号:
    MR/X004171/1
  • 财政年份:
    2023
  • 资助金额:
    $ 5.19万
  • 项目类别:
    Research Grant
From 'inclusion' to 'ownership': Learnings from a care provision program for unaccompanied minors in Montreal
从“包容”到“所有权”:蒙特利尔无人陪伴未成年人护理服务项目的经验教训
  • 批准号:
    474592
  • 财政年份:
    2022
  • 资助金额:
    $ 5.19万
  • 项目类别:
    Studentship Programs
Association of Canada's Provincial Bans on Electronic Cigarette Sales to Minors With Electronic Cigarette Use Among Youths
加拿大各省禁止向未成年人销售电子烟 青少年使用电子烟
  • 批准号:
    421912
  • 财政年份:
    2020
  • 资助金额:
    $ 5.19万
  • 项目类别:
Investigating the relationship between head injury and aggression in minors over time
随着时间的推移调查未成年人头部受伤与攻击行为之间的关系
  • 批准号:
    2445620
  • 财政年份:
    2020
  • 资助金额:
    $ 5.19万
  • 项目类别:
    Studentship
The investigation of change mechanisms in trauma-focused interventions for traumatized refugee minors
受创伤难民未成年人创伤干预措施变革机制的调查
  • 批准号:
    447787115
  • 财政年份:
    2020
  • 资助金额:
    $ 5.19万
  • 项目类别:
    WBP Fellowship
The impact and effectiveness of mentoring projects with unaccompanied minors
无人陪伴未成年人辅导项目的影响和有效性
  • 批准号:
    2434327
  • 财政年份:
    2020
  • 资助金额:
    $ 5.19万
  • 项目类别:
    Studentship
Exploring the lived experience of death and dying for mature minors in Canada.
探索加拿大成熟未成年人的死亡和临终经历。
  • 批准号:
    439756
  • 财政年份:
    2020
  • 资助金额:
    $ 5.19万
  • 项目类别:
    Operating Grants
Fast Algorithm for Enumerating Graph Minors in a Graph
枚举图中次要图的快速算法
  • 批准号:
    19J21000
  • 财政年份:
    2019
  • 资助金额:
    $ 5.19万
  • 项目类别:
    Grant-in-Aid for JSPS Fellows
Graph minors, topological minors, and immersions
图次要项、拓扑次要项和浸入式
  • 批准号:
    1929851
  • 财政年份:
    2018
  • 资助金额:
    $ 5.19万
  • 项目类别:
    Continuing Grant
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了