图的线性荫度、均匀染色及其相关问题的研究

基本信息
批准号:11401386
项目类别:青年科学基金项目
资助金额:22.00
负责人:陈宏宇
学科分类:
依托单位:上海应用技术大学
批准年份:2014
结题年份:2017
起止时间:2015-01-01 - 2017-12-31
项目状态: 已结题
项目参与者:谭香,王慧娟,高毓平,张文文
关键词:
均匀染色线性荫度均匀点荫度全染色
结项摘要

Graph coloring theory occupies an important position in the study of graph theory, and it has important applications in the optimization, computer theory, network design, etc. In this project we will research some classic problems of graph colorings: the linear arboricity, total coloring, equitable coloring and the extension of them: the linear k-arboricity, equitable vertex arboricity etc. Our aim is to determine the linear arboricity, total chromatic number, equitable chromatic number, equitable vertex arboricity of some large classes of graphs such as planar grpahs, graphs embedded in surfaces, solve or partly solve some related famous conjectures. This project mainly includes two parts, one part is the classic problems of graph coloring, the other part is the extension of them. The solutions of the problems in this project will promote the development of graph coloring.

图的染色理论在图论研究中占有重要的地位,在最优化、计算机理论、网络设计等方面都有着重要的应用。本项目计划研究几个经典的图的染色问题:线性荫度、全染色、均匀染色以及它们的推广:线性k-荫度,均匀点荫度等。我们力求确定一些大的图类,如平面图、可嵌入到曲面上的图的线性荫度,全色数,均匀色数,均匀点荫度等,解决或部分解决相关的几个著名猜想。本项目研究的内容主要包括两个部分:一部分是图论中经典的染色问题,另一部分是这几类经典染色问题的推广,问题的解决对于图的染色理论将有较大的促进作用。

项目摘要

图的染色理论在图论研究中占有重要的地位,在最优化、计算机理论、网络设计等方面都有着重要的应用。本项目旨在研究几类经典的染色问题:线性荫度、全染色、均匀染色以及它们的推广:线性k-荫度,均匀点荫度等,具体包括:1. 平面图、可嵌入到曲面上的图的线性荫度、线性k- 荫度; 2. 全染色猜想;3. 平面图、1-平面图、可嵌入到曲面上的图的均匀色数;4. 均匀点荫度猜想。.对于问题1,利用欧拉公式和权转移的方法给出了5-圈不与3-圈或4-圈相邻的平面图的线性2-荫度的一个较小的上界,4-圈不共点的平面图的线性2-荫度的一个上界,这两个结果都已经以论文的形式发表。另外对于不含有相交5-圈的平面图的线性2-荫度,也给出了它的一个较小的上界,这一结果已经投稿。.对于问题2,通过构造平面图的一些特殊结构,利用欧拉公式证明了如下图形的全色数等于Delta+1:(1)最大度Delta至少为7且不含有相邻5-圈的平面图,(2)最大度Delta至少为6且不含有相交4-圈和相交5-圈的平面图,(3)最大度Delta至少为6且不含有6-圈和相邻5-圈的平面图,(4)最大度Delta至少为8且不包含含有两条弦的相邻i-圈和j-圈,其中i,j属于{5,6,7}的平面图,(5)最大度Delta大于等于8的平面图且对于每一个顶点v都存在两个整数i,j属于{3,4,5,6,7},使得v都不与相邻的i-圈和j-圈相关联。另外我们还证明了最大度Delta至少为8且不含有弦5-圈的平面图的列表边色数等于Delta,列表全色数等于Delta+1. 这些结果也都已经以论文的形式发表。.对于问题3,因为k-退化图和k-染色图之间的关系需要证明,而且研究均匀染色需要用到其中的一些结论,所以此问题还在进一步研究中。.对于问题4,吴建良等人在2013年提出了均匀点荫度猜想,即:任何简单图G的点集合都可以均匀的分成m个子集,并且每一个子集都是一个导出森林,其中Delta(G)表示图G最大度,m是一个整数,且满足$m\geq\lceil\frac{Delta+1}{2}\rceil$。我们证明了对于5-退化图,该猜想成立。该结果也已经以论文的形式发表。.此外我们还研究了1-2-3猜想和平面图、曲面图的列表单射染色,相关结果见发表的论文。

项目成果
{{index+1}}

{{i.achievement_title}}

{{i.achievement_title}}

DOI:{{i.doi}}
发表时间:{{i.publish_year}}

暂无此项成果

数据更新时间:2023-05-31

其他相关文献

1

带有滑动摩擦摆支座的500 kV变压器地震响应

带有滑动摩擦摆支座的500 kV变压器地震响应

DOI:10.13336/j.1003-6520.hve.20200528028
发表时间:2021
2

基于腔内级联变频的0.63μm波段多波长激光器

基于腔内级联变频的0.63μm波段多波长激光器

DOI:10.3788/CJL201946.0801003
发表时间:2019
3

信息熵-保真度联合度量函数的单幅图像去雾方法

信息熵-保真度联合度量函数的单幅图像去雾方法

DOI:10.3724/SP.J.1089.2019.17435
发表时间:2019
4

具有随机多跳时变时延的多航天器协同编队姿态一致性

具有随机多跳时变时延的多航天器协同编队姿态一致性

DOI:10.7641/CTA.2018.70969
发表时间:2018
5

现代优化理论与应用

现代优化理论与应用

DOI:10.1360/SSM-2020-0035
发表时间:2020

陈宏宇的其他基金

批准号:11226291
批准年份:2012
资助金额:3.00
项目类别:数学天元基金项目

相似国自然基金

1

嵌入图的全染色和线性荫度

批准号:11671053
批准年份:2016
负责人:王艺桥
学科分类:A0409
资助金额:48.00
项目类别:面上项目
2

图的均匀染色及其相关问题的研究

批准号:11871055
批准年份:2018
负责人:张欣
学科分类:A0409
资助金额:48.00
项目类别:面上项目
3

关于图的线性荫度一个猜想的研究

批准号:11226291
批准年份:2012
负责人:陈宏宇
学科分类:A0409
资助金额:3.00
项目类别:数学天元基金项目
4

图的距离染色及其相关问题的研究

批准号:11771443
批准年份:2017
负责人:苗连英
学科分类:A0409
资助金额:48.00
项目类别:面上项目