Density and Edge Coloring

密度和边缘着色

基本信息

项目摘要

A graph is a mathematical structure that can be used to model relationships between objects. Take social networking as an example: each person in the network could be considered as a point, called a vertex, and two people are joined by an edge if they are friends. Edge-coloring studies the ways one can color edges of a graph under some restrictions. For example, a proper edge-coloring is an assignment of colors to the edges of a graph so that no two edges sharing the same vertex have the same color. One important problem is to find the smallest number of colors possible that can be used for a proper edge-coloring. In this project, the PI is planning to address open problems in edge-coloring as well as deriving efficient algorithms for graph coloring problems. Theoretical results and algorithms in edge-coloring have important applications in network problems, communication problems, scheduling problems, and many other optimization problems. Density as a graph parameter is involved in many open problems in edge-coloring. The main goal of this project is to apply density-related techniques such as a generalization of the Tashkinov tree method obtained in attacking the Goldberg-Seymour conjecture, and a generalized Kempe Change method developed in exploring the Hilton-Zhao conjecture, to attack the following density-related problems: (1) the Hilton-Zhao conjecture and the overfull conjecture; (2) Gupta’s co-density conjecture; (3) Goldberg’s generalization of the total coloring conjecture for multigraphs; and (4) finding efficient algorithms to color graphs with the optimal number of colors in the conjectures above. The PI is also hoping to develop new density-related techniques through exploring the above problems.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计划解决边缘着色中的开放问题,并为图着色问题提供有效的算法。边着色的理论结果和算法在网络问题、通信问题、调度问题和许多其他优化问题中都有重要的应用。密度作为一个图参数,涉及到许多边着色的开放问题。本项目的主要目标是应用密度相关的技术,如在攻击Goldberg-Seymour猜想中获得的Tashkinov树方法的推广,以及在探索Hilton-Zhao猜想中开发的广义Kempe变化方法,来攻击以下与密度相关的问题:(1)Hilton-Zhao猜想和过满猜想;(2) Gupta共密度猜想;(3) Goldberg对多图全着色猜想的推广;(4)找到有效的算法,在上面的猜想中使用最优的颜色数来给图上色。PI还希望通过探索上述问题来开发新的密度相关技术。该奖项反映了美国国家科学基金会的法定使命,并通过使用基金会的知识价值和更广泛的影响审查标准进行评估,被认为值得支持。

项目成果

期刊论文数量(7)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
Decomposition of class II graphs into two class I graphs
将 II 类图分解为两个 I 类图
  • DOI:
    10.1016/j.disc.2023.113610
  • 发表时间:
    2023
  • 期刊:
  • 影响因子:
    0.8
  • 作者:
    Cao, Yan;Jing, Guangming;Luo, Rong;Mkrtchyan, Vahan;Zhang, Cun-Quan;Zhao, Yue
  • 通讯作者:
    Zhao, Yue
Independence number of edge‐chromatic critical graphs
边独立数-色临界图
  • DOI:
    10.1002/jgt.22825
  • 发表时间:
    2022
  • 期刊:
  • 影响因子:
    0.9
  • 作者:
    Cao, Yan;Chen, Guantao;Jing, Guangming;Shan, Songling
  • 通讯作者:
    Shan, Songling
The core conjecture of Hilton and Zhao
希尔顿和赵的核心猜想
  • DOI:
    10.1016/j.jctb.2024.01.004
  • 发表时间:
    2024
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Cao, Yan;Chen, Guantao;Jing, Guangming;Shan, Songling
  • 通讯作者:
    Shan, Songling
A note on Goldberg's conjecture on total chromatic numbers
关于戈德堡总色数猜想的注解
  • DOI:
    10.1002/jgt.22771
  • 发表时间:
    2021
  • 期刊:
  • 影响因子:
    0.9
  • 作者:
    Cao, Yan;Chen, Guantao;Jing, Guangming
  • 通讯作者:
    Jing, Guangming
Overfullness of edge‐critical graphs with small minimal core degree
边缘过度充满——最小核心度较小的临界图
  • DOI:
    10.1002/jgt.23069
  • 发表时间:
    2023
  • 期刊:
  • 影响因子:
    0.9
  • 作者:
    Cao, Yan;Chen, Guantao;Jing, Guangming;Shan, Songling
  • 通讯作者:
    Shan, Songling
{{ 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 }}

Guangming Jing其他文献

Precoloring extension of Vizing’s Theorem for multigraphs
多重图的 Vizing 定理的预着色扩展
  • DOI:
    10.1016/j.ejc.2024.104037
  • 发表时间:
    2024-12-01
  • 期刊:
  • 影响因子:
    0.900
  • 作者:
    Yan Cao;Guantao Chen;Guangming Jing;Xuli Qi;Songling Shan
  • 通讯作者:
    Songling Shan
DENSITY AND CHROMATIC INDEX, AND MINIMUM RANKS OF SIGN PATTERN MATRICES
  • DOI:
  • 发表时间:
    2019
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Guangming Jing
  • 通讯作者:
    Guangming Jing
Maximum Resistance-Harary index of cacti
仙人掌最大阻力-哈里指数
  • DOI:
    10.1016/j.dam.2018.05.042
  • 发表时间:
    2018-12
  • 期刊:
  • 影响因子:
    1.1
  • 作者:
    Wei Fang;Yi Wang;Jia-Bao Liu;Guangming Jing
  • 通讯作者:
    Guangming Jing
Rank conditions for sign patterns that allow diagonalizability
允许对角化的符号模式的排名条件
  • DOI:
    10.1016/j.disc.2019.111798
  • 发表时间:
    2020-05
  • 期刊:
  • 影响因子:
    0.8
  • 作者:
    Xin-Lei Feng;Wei Gao;Frank J. Hall;Guangming Jing;Zhongshan Li;Chris Zagrodny;Jiang Zhou
  • 通讯作者:
    Jiang Zhou

Guangming Jing的其他文献

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

{{ truncateString('Guangming Jing', 18)}}的其他基金

Density and Edge Coloring
密度和边缘着色
  • 批准号:
    2001130
  • 财政年份:
    2020
  • 资助金额:
    $ 9.4万
  • 项目类别:
    Continuing Grant

相似国自然基金

Edge-on型X射线能谱探测器及可重构能谱解析技术研究
  • 批准号:
    61674115
  • 批准年份:
    2016
  • 资助金额:
    62.0 万元
  • 项目类别:
    面上项目

相似海外基金

CAREER: Adaptive Deep Learning Systems Towards Edge Intelligence
职业:迈向边缘智能的自适应深度学习系统
  • 批准号:
    2338512
  • 财政年份:
    2024
  • 资助金额:
    $ 9.4万
  • 项目类别:
    Continuing Grant
Collaborative Research: Conference: DESC: Type III: Eco Edge - Advancing Sustainable Machine Learning at the Edge
协作研究:会议:DESC:类型 III:生态边缘 - 推进边缘的可持续机器学习
  • 批准号:
    2342498
  • 财政年份:
    2024
  • 资助金额:
    $ 9.4万
  • 项目类别:
    Standard Grant
Research Infrastructure: KCV EDGE (Equitable and Diverse Grant Ecosystem)
研究基础设施:KCV EDGE(公平且多样化的资助生态系统)
  • 批准号:
    2345142
  • 财政年份:
    2024
  • 资助金额:
    $ 9.4万
  • 项目类别:
    Cooperative Agreement
Collaborative Research: Learning for Safe and Secure Operation of Grid-Edge Resources
协作研究:学习电网边缘资源的安全可靠运行
  • 批准号:
    2330154
  • 财政年份:
    2024
  • 资助金额:
    $ 9.4万
  • 项目类别:
    Standard Grant
Deep Adder Networks on Edge Devices
边缘设备上的深加法器网络
  • 批准号:
    FT230100549
  • 财政年份:
    2024
  • 资助金额:
    $ 9.4万
  • 项目类别:
    ARC Future Fellowships
Cutting-edge bio-material for 3D printed bone fixation plates
用于 3D 打印骨固定板的尖端生物材料
  • 批准号:
    24K20065
  • 财政年份:
    2024
  • 资助金额:
    $ 9.4万
  • 项目类别:
    Grant-in-Aid for Early-Career Scientists
MHDSSP: Self-sustaining processes and edge states in magnetohydrodynamic flows subject to rotation and shear
MHDSSP:受到旋转和剪切作用的磁流体动力流中的自持过程和边缘状态
  • 批准号:
    EP/Y029194/1
  • 财政年份:
    2024
  • 资助金额:
    $ 9.4万
  • 项目类别:
    Fellowship
Open Access Block Award 2024 - Edge Hill University
2024 年开放获取区块奖 - Edge Hill 大学
  • 批准号:
    EP/Z532307/1
  • 财政年份:
    2024
  • 资助金额:
    $ 9.4万
  • 项目类别:
    Research Grant
SBIR Phase I: Novel Self-Closing, Transcatheter, Edge-to-Edge Repair Device to Percutaneously Treat Tricuspid Valve Regurgitation Using Jugular or Femoral Vein Access
SBIR 第一阶段:新型自闭合、经导管、边对边修复装置,利用颈静脉或股静脉通路经皮治疗三尖瓣反流
  • 批准号:
    2322197
  • 财政年份:
    2024
  • 资助金额:
    $ 9.4万
  • 项目类别:
    Standard Grant
Optimizing Intelligent Vehicular Routing with Edge Computing through Multi-Agent Reinforcement Learning
通过多智能体强化学习利用边缘计算优化智能车辆路由
  • 批准号:
    24K14913
  • 财政年份:
    2024
  • 资助金额:
    $ 9.4万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了