位置：立项数据库 > 立项详情页
边着色图的单色和异色子图及顶点集合划分问题
  • 项目名称：边着色图的单色和异色子图及顶点集合划分问题
  • 项目类别：面上项目
  • 批准号：10671102
  • 申请代码：A011602
  • 项目来源：国家自然科学基金
  • 研究期限：2007-01-01-2009-12-31
  • 项目负责人：李学良
  • 负责人职称：教授
  • 依托单位：南开大学
  • 批准年度：2006
中文摘要：

边着色图的单色和异色子图（圈、路、树、匹配等）的研究，以及用最少的某种单色或异色子图去划分该图的顶点集合的研究起源于匈牙利学派，国际数学大师Erdos 在九十年代前后有多篇文章做这方面的研究，从事过这方面研究的其他重要人物有Alon、Gyarfas、Haxell、Reed、 Thomassen、Tuza等，这方面的研究还与Ramsey 理论有密切的联系，因此我们选择的研究课题在图论学科中具有重要的理论意义。从已发表的文章来看，这方面的研究难度比较大，研究进展也比较缓慢。本项目拟解决在色度数及色领域并的条件下最长异色路的最佳下界、异色圈问题。研究最大或完美异色匹配问题。用概率方法研究随机边着色下的各种单色和异色子图的存在概率问题。研究顶点集合的某种单色或异色子图的最佳划分问题，研究最佳划分的算法复杂性、多项式时间算法、近似算法等组合优化问题。这些研究将成为图论学科中新的热点问题。

中文主题词： 单色子图;异色子图;顶点集合划分;算法;复杂性
结论摘要：

英文主题词Monochromatic subgraph; Heterochromatic subgraph; Partition of vertex set; Algorithm; Computational complexity

成果综合统计
成果类型
数量
  • 期刊论文
  • 会议论文
  • 专利
  • 获奖
  • 著作
  • 49
  • 1
  • 0
  • 2
  • 0
期刊论文
The heterochromatic matchings in edge-colored bipartite graphs
Complete solution for the rainbow numbers of matchings
Bipartite rainbow numbers of matchings
Rainbow number of matchings in regular bipartite graphs
General Randic index on trees with a given order and diameter
Maximum energy trees with two maximum degree vertices
(n;m)-Graphs with maximum zeroth-order general Randic index for alpha in (-1, 0)
On bipartite graphs with minimal energy
三种新变形的全一问题
Hypoenergetic trees
On the determination problem for P_4-transformation of graphs
Integral trees of diameter 6
Connected (n,m)-graphs with minimum and maximum zeroth-order general Randic index
More on "Solutions to two unsolved questions on the best upper bound for the Randic index R_{-1} of
On the minimum monochromatic or multicolored subgraph partition problems
On unicyclic conjugated molecules with minimal energies
NP-completeness of 4-incidence colorability of semi-cubic graphs
The general σ all ones problem for trees
Some families of integral graphs
Graphs with the second largest number of maximal independent sets
Binary construction of quantum codes of minimum distances five and six
More on the best upper bound for the Randic index R_{-1} of trees
Minimum general Randic index on chemical trees with given order and number of pendent vertices
Partitioning 3-edge-colored complete equi-bipartite graphs by monochromatic trees under a color degr
Nonexistence of triples of nonisomorphic connected graphs with isomorphic connected P_3-graphs
The 2nd order conditional 3-coloring of claw-free graphs
On bicyclic graphs with maximal energy
The neibor-scatering number can be computed in polynomial time for interval graphs
The spread of unicyclic graphs with given size of maximum matchings
Chromaticity of the complements of some sparse graphs
路图与线图的一个综述
Monochromatic and heterochromatic subgraphs in edge-colored graphs - A survey
Heterochromatic tree partition numbers for complete bipartite graphs
A survey on the Randic index
Vertex partitions of r-edge-colored graphs
Path graphs versus line graphs - a survey
Color neighborhood union conditions for long heterochromatic paths in edge-colored graphs
On the complexity of dominating set problems related to the minimum all-ones problem
Corrections of proofs for Hansen and Mélot's two theorems
Sufficient conditions for the existence of perfect heterochromatic matchings in colored graphs
The binding number of a digraph
会议论文
Weighted Lee algorithm on rectilinear Steiner tree with obstacles and boundary
获奖
直径为5和6的整谱树
直径为5和6的整谱树
相关项目
边染色图中的异色子图问题
期刊论文 5
保密计算服务的计算模型、算法与质量评价研究
期刊论文 36 会议论文 7 专利 2 著作 1
基因组比较问题的算法与复杂性
期刊论文 14 会议论文 5 获奖 3
连通因子理论及其在网络和公开钥密码学中的应用
期刊论文 35 会议论文 13
基因组重组比较算法与复杂性研究
期刊论文 15 会议论文 4 著作 1
排序和路线问题复杂性和在线算法
期刊论文 16
未来移动通信射频信号非线性自适应预失真技术研究
期刊论文 14 会议论文 18
单机批调度中的算法与计算复杂性研究
期刊论文 13 会议论文 9
面向协同商务制造资源管理的关键技术研究
期刊论文 16 会议论文 12 著作 1
李学良的项目
最小全一问题的算法与复杂性及其相关问题的研究
组合数学、特殊函数与物理
　组合数学
图的彩虹连通性与树-连通性
期刊论文 69 著作 3
全一问题的最优解及相关问题的算法与复杂性研究
期刊论文 11 著作 1
图的彩虹连通与广义连通度
期刊论文 1