超圖的2-可染色性和圖的控制集問題

《超圖的2-可染色性和圖的控制集問題》是依託華東師範大學，由呂長虹擔任項目負責人的面上項目。

基本介紹

• 中文名：超圖的2-可染色性和圖的控制集問題
• 項目類別：面上項目
• 項目負責人：呂長虹
• 依託單位：華東師範大學

項目摘要

超圖的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-完備的，同時給出了頂點賦權樹的最小鄰域全控制集的線性時間算法。最後完整刻畫了鄰域全控制數等於裝填數的圖的結構。