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

项目名称： 图的子图横贯与子图回避染色

项目编号： No.11171207

项目类型： 面上项目

立项/批准年度： 2012

项目学科： 数理科学和化学

项目作者： 单而芳

作者单位： 上海大学

项目金额： 40万元

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

中文关键词： 团横贯；团染色；子图横贯；超图；界的估计

英文摘要：

英文关键词： clique-transversal；clique-coloring；subgraph-transversal；hypergraph；estimation of bound