超图的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: First,we shall concentrate on the essential extremal problem on the 2-colorability of hypergraph: given a n-uniform hypergraph H, determine m(n), the minimum possible number of edges of H such that it is not 2-colorable.We hopt to improve the upper and lower bounds on m(n); Secondly,using "slow recoloring" random method in the research on the 2-colorability of hypergraph and semidefinite program,we shall consider some variations of graph coloring. Thirdly, around the conjecture of Goddard and Henning in 2009 on the upper bound of paired-domination number of graphs, we shall estimate the bounds on paired-domination numbers of the various classes of graphs and characterize extremal graphs. We hope to imporve the known results. At last, we shall consider the power domination problem on chordal graphs and its subclasses from algorithmic aspects.

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

染色问题是图论和超图的一个经典的问题。在广义的 Ramsey 理论中，边染色图中特定单色子图（如圈，路，树等），特定划分或覆盖的存在性有很好的研究动机。相比图的边染色问题，超图的边染色问题更为复杂，研究的结果相对较少。本项目研究边染色超图的单色子图划分和覆盖问题，主要得到如下结果：.（1）证明了如果 n ≡ 2 mod (k − 1)，则每个 2-边染色完全 k-一致超图 Kn 一定存在两个顶点不交的红色和蓝色线性路覆盖 Kn 的所有顶点。这个结果肯定了 Gyarfas 和 Sarkozy 在 2013 年提出的关于边染色超图的单色路划分猜想：每个 2-边染色完全 k-一致超图 Kn一定存在两个顶点不交的红色和蓝色线性路覆盖 Kn 至少 n-k+2 个顶点。..（2）研究 2-边染色 k-一致完全超图Kn的覆盖问题并得到如下结果：对任意的 2-边染色 k-一致完全超图 Kn，它的所有顶点可以由两条不同颜色的单色线性路覆盖使得这两条路至多相交 k-2 个顶点，该结果中 k-2 是最优的。.. 图论中的控制集是运筹学中选址问题的一个自然的模型。由于不同的应用背景，学者们需要研需要研究不同类型的控制集问题。本项目主要研究配对控制集，电力控制集和邻域全控制集等这些控制集相关问题，具体结果如下： .(1)证明了 2009 年 Goddard 和 Henning 提出的关于配对控制集上界的猜想对 k (≥4)-正则图和无爪图成立，也即: 如果 G 是一个连通 k(≥4)-正则图或最小度不小于 3 的无爪图，则 G 的配对控制数不超过 4n/7。进一步地证明了如果 G 是一个连通的最小度不小于 4 的无爪图，则 G 的配对控制数不超过其顶点的数的一半。..（2）给出了 k-电力控制集在块图上的线性时间算法，推广了 Chang, Guo, Xu 等人的结果。否定了 Dorbec 等在 2013年提出的关于电力控制集的猜想，并给出了 4-正则无爪图的电力控制数紧的上界：如果 G 是阶数为 n 的连通 4-正则无爪图，则 G 的最小电力控制集的基数不超过 (n+1)/5。..（3）证明了邻域全控制集问题在二部图和分裂图上是 NP-完备的，同时给出了顶点赋权树的最小邻域全控制集的线性时间算法。最后完整刻画了邻域全控制数等于装填数的图的结构。