超图的2-可染色性和图的控制集问题

项目名称： 超图的2-可染色性和图的控制集问题

项目编号： No.11371008

项目类型： 面上项目

立项/批准年度： 2013

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

项目作者： 吕长虹

作者单位： 华东师范大学

项目金额： 50万元

中文摘要： 超图的2-可染色问题是超图染色的一个中心问题，图的控制集理论是目前图论研究的重要内容，也是运筹学选址问题的自然模型。本项目研究的核心内容包括：一、研究超图的2-可染色问题的一个重要的极值问题：一个至少拥有m(n)条边的 n-uniform 超图不是2-可染色的，则m(n)应为多少？本项目将围绕这个问题及相关问题进行研究，希望改进目前关于m(n)的上下界；二、利用超图2-可染色性研究中"slow recoloring"随机思想，结合半正定规划方法，研究图的各种染色问题；三、围绕Goddard和Henning在2009年关于配对控制数上界的猜想，考虑各种图类配对控制数上界估计和极图刻画，希望改进目前已知结果；四、考虑chordal graphs及其子图类上电力控制集问题算法复杂性、有效算法、近似算法等。

中文关键词： 2-染色超图；覆盖；配对控制集；电力控制集；邻域全控制集

英文摘要： The 2-colorability of hypergraphs is a central issue in hypergraph coloring. The domination problem play an important role on graph theory,it is also a natural model for many locating problems in operations research.The core of this project include: Firs

英文关键词： 2-coloring hypergraph；covering；paired-domination；power domination；neighborhood total domination