3-正则图的核理论及其应用
批准号:
11801522
项目类别:
青年科学基金项目
资助金额:
25.0 万元
负责人:
金利刚
依托单位:
学科分类:
A0409.图论及其应用
结题年份:
2021
批准年份:
2018
项目状态:
已结题
项目参与者:
亢莹利、蒋燚婷、林凯
国基评审专家1V1指导 中标率高出同行96.8%
结合最新热点,提供专业选题建议
深度指导申报书撰写,确保创新可行
指导项目中标800+,快速提高中标率
微信扫码咨询
中文摘要
在图的完美匹配理论中,Fulkerson猜想是其中的一个核心猜想。Fulkerson猜想断言:每个无桥的3-正则图都有六个完美匹配,使得每条边包含在其中的恰好两个完美匹配上。3-正则图的核理论是近些年引入的一种新的研究方法。本项目将应用3-正则图的核理论来研究Fulkerson猜想及其相关联的另外三个重要猜想:Petersen着色猜想、Berge猜想和Fan-Raspaud猜想。目前,这四个猜想仅在非常有限的图类上得到了验证。本项目将考虑一个与Petersen着色猜想相关的问题,期望得到该问题的一个肯定的解答。对于其余三个猜想,本项目将通过核给出一些更为宽泛的图类,并论证猜想在这些图类上是成立的。一方面,本项目运用3-正则图的核理论来推动对以上四个猜想的研究;另一方面,在研究过程中,核理论本身也将得到丰富。
英文摘要
In the theory on perfect matchings of graphs, Fulkerson Conjecture is a conjecture in the central place. Fulkerson Conjecture states that every bridgeless cubic graph has six perfect matchings such that each edge is contained in precisely two of them. The theory on cores of cubic graphs was introduced recently. It provides a new way to consider some problems. In this project, we will apply the theory on cores to study Fulkerson Conjecture and three related conjectures, including Petersen Coloring Conjecture, Berge Conjecture and Fan-Raspaud Conjecture. So far, these four conjectures were verified for only a few classes of cubic graphs. First, we will consider a question related to the Petersen coloring conjecture, and expect to give a positive answer to this question. Then, for each remaining conjecture, we will search for a more relaxed condition in terms of cores under which this conjecture holds. On one hand, this project applies the theory on cores of cubic graphs to study these four conjectures. On the other hand, this study will enrich the theory on cores itself.
本项目考虑图的完美匹配理论中的2个重要猜想:Petersen着色猜想和Berge猜想,其中Petersen着色猜想强于Berge猜想。鉴于平面图存在以下等价关系:四色定理等价于命题“任意的无桥3-正则平面图的边集可剖分为3个完美匹配”,本项目还考虑四色定理的推广问题和平面图的3-色可染性。. 首先,关于Petersen着色猜想,我们证明了:每一个无桥3-正则图G存在正常的5-边着色,使得至多μ_3(G)条边为非规范边(因此,至少27/35比例的边为规范边)。该结论较好地解答了Petersen着色猜想的弱化问题。该结论不仅较大地改进了已知结果,也引起其他学者的关注和对更一般的k-边着色情形下类似问题的探讨。. 其次,关于Berge猜想,我们证明了:对任意的r-图,用k个完美匹配组成的边覆盖在整个边集中的最大占比m(r,k)的一个下界。特别地,若取k=2r-1,该结论为广义Berge猜想的弱化问题提供一个初步的解答,即m(r,k)至少为86.5%。. 此外,关于四色定理的推广,我们提出更为一般的广义符号图染色(即S-k-染色)的概念,并证明了四色定理在S-4-染色的框架下不能作任何加强。. 最后,关于平面图的3-色可染性,我们证明了:任意不含有4-圈和6-圈的简单平面图都是(1,0,0)-可染的。该结论改进了数个已知结果,是Steinberg猜想的类似问题关于(1,0,0)-可染性的第一个结论。
期刊论文列表
专著列表
科研奖励列表
会议论文列表
专利列表
DOI:10.1016/j.ejc.2020.103198
发表时间:2021-02
期刊:Eur. J. Comb.
影响因子:--
作者:Li-gang Jin;T. Wong;Xuding Zhu
通讯作者:Li-gang Jin;T. Wong;Xuding Zhu
Partially normal 5-edge-colorings of cubic graphs
立方图的部分正态 5 边着色
DOI:10.1016/j.ejc.2021.103327
发表时间:2019-11
期刊:European Journal of Combinatorics
影响因子:1
作者:Ligang Jin;Yingli Kang
通讯作者:Yingli Kang
DOI:10.4310/joc.2020.v11.n3.a2
发表时间:2015-09
期刊:Journal of Combinatorics
影响因子:0.3
作者:Li-gang Jin;E. Steffen
通讯作者:Li-gang Jin;E. Steffen
国内基金
海外基金















{{item.name}}会员


