图的子图横贯与子图回避染色

结题报告

项目介绍

AI项目解读

基本信息

批准号：
11171207
项目类别：
面上项目
资助金额：
40.0万
负责人：
单而芳
依托单位：
上海大学
学科分类：
A0409.图论及其应用
结题年份：
2015
批准年份：
2011
项目状态：
已结题
起止时间：
2012-01-01 至2015-12-31

项目参与者：
康丽英；梁作松；汪定国；洪艳梅；赵衍才；黄申为；王鹤超；孙强；姜恒武；
关键词：
子图回避染色团染色子图横贯界的估计团横贯

项目摘要

在图论中，图的子图横贯概念既是超图理论中横贯概念的特例，又可看作图的团横贯概念的推广，而图的子图回避染色问题是与子图横贯密切相关的一个问题，可看作图的团染色问题的推广。图的团横贯问题在上世纪90年初被Erd?s、Gallai和Tuza所研究，它是图论研究的重要内容，在通讯网络和社会网络拓扑模型的研究中具有广泛的应用。本项目旨在研究图的子图横贯数和子图回避色数界的估计问题和相关的极值问题。主要以图论和组合优化为工具，围绕组合数学家Erd?s等提出的团横贯数界的估计问题和最近提出的一些未解决问题开展下列研究工作：搞清楚子图回避染色的计算法复杂性；在一般图上建立子图横贯数和子图回避色数的界并刻画相应的极值图类；在某些重要图类上建立图的团横贯数和团色数的界并刻画相应的极值图类；讨论这些参数与经典图参数之间的关系。本项目的研究对深刻揭示图论的结构性质具有重要意义。

结项摘要

图的子图横贯是图论研究的重要内容之一，它涉及图论中的覆盖、匹配、控制集、独立集合染色等基本概念，对深刻揭示图的结构性质具有重要意义,在通讯网络和社会网络等领域均具有广泛的应用。项目研究的主要内容是图的团横贯和团染色问题。确定子图横贯数、团横贯数和团色数的界并刻画极值图类，探索这些参数与其他图参数之间的关系。. Mohar等证明了平面图是强3-团可染色的. Erdos等曾提出估计平面图等图类的团横贯数的界. 我们建立了外平面图团横贯数的紧的上界. 其次，证明了除奇圈外，每个无爪平面图是2-团可染色的。作为推论获得了无爪平面图的团横贯数的紧的上界，该结果部分回答了Erdos等提出的估计平面图团横贯数的界的问题。在上述结果的基础上，我们推广Mohar等的结果到K5-minor-free图上，同时，给出了此类图的团染色问题的多项式时间算法。. 对不含K4无爪4-正则图，首先给出了其团横贯数的下界并刻划了极值图类；其次，对2-连通的无爪K4-free的4-正则图，我们证明了其团横贯数恰好等于[|V(G)|/3]. 对3-正则图，通过证明每个至多含有两条割边的3-正则图存在一个完美匹配含有每个3-圈的恰好一条边，证明了此类图的线图的横贯数恰好为|E(G)|/3.同时证明了每个3-正则图的线图的横贯数上、下界。此外，按照图的围长，给出了3-正则图的团横贯数的可达上界。证明了不含三角形的图的线图的团横贯数不超过其补图的色数。给出了任意两个图的团色数与它们通过笛卡尔积、Kronecker积、强直积或字典积运算后得到的积图的团色数之间的关系。对图的符号最大团横贯函数，建立了的任意图和团数为k的正则图的符号最大团横贯数的可达下界，并刻划了极值图类。图G的Alcuin数是指冲突图G具有可行运输方案时船的最小容量.我们确定了最大度不超过5的图的Alcuin数，并将这一问题推广到超图上。. Cerioli等提出了圆弧图的团染色问题的多项式时间算法。我们进一步给出了圆弧图的团染色问题的线性时间算法，从而解决了Cerioli等提出的一个未解决问题。对最大度至多为4的图的团横贯问题，我们提出了一个多项式时间算法。证明了对围长为3的3次平面图上，团横贯和团独立集问题是NP-完全的，同时给出了3-正则图的近似算法。