图的边染色与匹配问题

结题报告

项目介绍

AI项目解读

基本信息

批准号：
12226303
项目类别：
数学天元基金项目
资助金额：
20.0万
负责人：
王维凡
依托单位：
浙江师范大学
学科分类：
结题年份：
2023
批准年份：
2022
项目状态：
已结题
起止时间：
2022 至2023

项目参与者：
王维凡；
关键词：
邻点区别边染色无圈边染色强边染色匹配图染色

项目摘要

Graph coloring and matching are important branches of graph theory, which have wide applications in practical problems. In this project, starting with the structural properties of graphs, and aiming at several well-known conjectures, we investigate the strong edge coloring, star edge coloring, acyclic edge coloring, neighbor-distinguishing edge coloring, matching well as related problems. It will be shown or partially shown that a simple graph is 1.7Δ^2-strong edge colorable, 3Δ-acyclic edge colorable, and 1.5Δ-neighbor-distinguishing edge colorable. The following results will also be proved: (1) A 1-planar graph is 14Δ-strong edge colorable and (Δ+c)-acyclic edge colorable; (2) A planar graph of girth at least five is (Δ+c)-strict-neighbor-distinguishing edge colorable; (3) A 3-degenerate chordal graph is (Δ+c)-acyclic edge colorable. We will also characterize those extremal graphs with maximum spectral radius in some families of graphs with prescribed matching number, and calculate the matching umber and strong matching number in a graph. The 3-5 papers will be completed after the project ends.

图的染色与匹配理论是图论研究的重要内容，在实际问题中有广泛应用。本项目从图的结构性质入手，围绕着几个公开问题，展开对图的强边染色、星边染色、无圈边染色、邻点区别边染色、图的匹配及相关问题的系统研究。力争证明或部分证明简单图是1.7Δ^2-强边可染的，3Δ-无圈边可染的，和1.5Δ-邻点区别边可染的；证明1-平面图是14Δ-强边可染的，(Δ+c)-无圈边可染的；证明围长至少为5的平面图是(Δ+c)-严格邻点区别边可染的；证明3-退化的弦图满足无圈边染色猜想；刻画匹配数限定的一些图族中谱半径达到最大的极图以及计算图中的匹配数和强匹配数。项目结题后完成学术论文3-5篇。

结项摘要

图的染色与匹配理论是图论研究的重要内容，在实际问题中有广泛应用。本项目从图的结构性质入手，围绕着几个公开问题，展开对图的强边染色、邻点区别边染色、点荫度、奇染色、匹配及相关问题的研究。证明了以下几个主要结果：（1）Δ=4的无爪图是17-强边可染的；（2）一般图的严格邻点区别边色数至多为3Δ-1，3-连通平面图的严格邻点区别边色数至多Δ+23；（3）1-平面图的奇色数至多为13；（4）没有相邻3-圈的平面图的点荫度至多为2。此外，刻画了给定匹配数的一些图族中谱半径达到最大的极图以及计算图中的匹配数和强匹配数。2023年我们发表了相关学术论文12篇。