《Discrete Mathematics》：Linear recoloring diameter of degenerate chordal graphs and bounded treewidth graphs
編輯推薦：
本文綜述了在圖的重構(gòu)配置圖Rt(G)中，關(guān)于t-重著色直徑的最新研究進(jìn)展。文章聚焦于d-退化圖和樹寬至多為k的圖類，系統(tǒng)梳理了不同參數(shù)t條件下（如t ≥ d+2, t ≥ (3/2)(d+1), t ≥ 2d+2等），t-重著色直徑從無限變?yōu)橛邢蕖挠邢拮優(yōu)橹炼喽危∣(n2)），以及最終達(dá)到最優(yōu)線性界（O(n)）的相變閾值。特別強(qiáng)調(diào)了作者在d-退化弦圖和樹寬有界圖類中，將線性直徑的條件改進(jìn)至t ≥ 2d+1和t ≥ 2k+1的核心結(jié)論，這推廣并改進(jìn)了Bartier等人關(guān)于樹寬為2的圖的結(jié)果。
亮點(diǎn) (Highlights)
- •
對于d-退化弦圖，我們證明了當(dāng)t ≥ 2d + 1時(shí)，其t-重著色直徑為O(n)（線性）。
- •
對于樹寬至多為k的圖，我們證明了當(dāng)t ≥ 2k + 1時(shí)，其t-重著色直徑為O(n)（線性）。
- •
這一結(jié)果推廣了先前關(guān)于樹寬至多為2的圖的結(jié)論。
討論 (Discussion)
這里自然產(chǎn)生一個(gè)問題：定理1.2和推論1.3中的界是否緊？Bartier, Bousquet和Heinrich在[1]中也提出了這個(gè)問題。令μ(k)（相應(yīng)地，ν(k)）為最小整數(shù)，使得對于任何樹寬至多為k（相應(yīng)地，k-退化且弦圖）的圖G，當(dāng)t ≥ μ(k)（相應(yīng)地，t ≥ ν(k)）時(shí)，G的t-重著色直徑至多為線性。定理1.2和推論1.3表明μ(k), ν(k) ≤ 2k + 1。
在[4]中，Bonamy, Johnson, Lignos, Patel和Paulusma構(gòu)建了一個(gè)樹寬為2的圖G（實(shí)際上是一個(gè)外平面圖），并證明了其4-重著色直徑是Ω(n2)。由于樹寬為2的圖是1-退化的，這意味著ν(1) ≥ 5。結(jié)合我們的結(jié)果ν(1) ≤ 3（因?yàn)閷τ赿=1，2d+1=3），我們可以得到ν(1) ∈ {3,4,5}。然而，[4]中的例子表明ν(1) ≥ 4，因?yàn)閠=3時(shí)直徑可能是Ω(n2)。因此，我們有ν(1) ∈ {4,5}。目前尚不清楚ν(1)的確切值是4還是5。對于樹寬為2的圖，我們知道當(dāng)t=4時(shí)，重著色直徑是Ω(n2)，而當(dāng)t ≥ 5時(shí)，重著色直徑是O(n)。因此，μ(2) = 5。對于更大的k，μ(k)和ν(k)的下界是k+2，因?yàn)橐阎?dāng)t = k+1時(shí)，存在樹寬為k的圖（例如完全圖Kk+1）不是t-混合的（即Rt(G)不連通）。因此，我們有k+2 ≤ μ(k), ν(k) ≤ 2k+1。
問題 5.1. 確定μ(k)和ν(k)的精確值或更緊的界。
已知對于樹寬至多為k的圖，當(dāng)t ≥ k+2時(shí)，t-重著色直徑至多為O(n2)[2]，而當(dāng)t ≥ 2k+1時(shí)，t-重著色直徑為O(n)。一個(gè)有趣的開放問題是，是否存在一個(gè)函數(shù)f(k)，使得當(dāng)t ≥ f(k)時(shí)，對于樹寬至多為k的圖，其t-重著色直徑為O(n)，并且f(k)介于k+2和2k+1之間。更具體地說：
問題 5.2. 對于樹寬至多為k的圖，是否存在一個(gè)常數(shù)c（與k無關(guān)），使得當(dāng)t ≥ k + c時(shí)，t-重著色直徑是線性的？
對于弦圖和更一般的完美圖，Bonamy等人[4]證明了如果G是弦圖且可r-著色，那么當(dāng)t ≥ r+1時(shí)，t-重著色直徑至多為二次。由于d-退化圖是(d+1)-可著色的，我們知道對于d-退化弦圖，當(dāng)t ≥ d+2時(shí)，t-重著色直徑至多為二次。在本文中，我們證明了當(dāng)t ≥ 2d+1時(shí)，該直徑變?yōu)榫�性。一個(gè)自然的問題是，對于弦圖，二次界和線性界之間的閾值是多少。
問題 5.3. 確定最小的t，使得對于任意d-退化弦圖G，其t-重著色直徑為O(n)。
我們證明了t ≤ 2d+1。對于下界，已知存在d-退化弦圖（例如樹），當(dāng)t = d+2時(shí)，其直徑是Ω(n2)[4]。因此，這個(gè)閾值介于d+2和2d+1之間。
結(jié)論 (Conclusion)
在本文中，我們研究了d-退化弦圖和有界樹寬圖的t-重著色直徑。我們證明了當(dāng)t ≥ 2d+1時(shí)，d-退化弦圖的t-重著色直徑是線性的。作為推論，當(dāng)t ≥ 2k+1時(shí)，樹寬至多為k的圖的t-重著色直徑也是線性的。這一結(jié)果推廣了Bartier、Bousquet和Heinrich關(guān)于樹寬為2的圖的結(jié)論[1]。我們還在討論部分提出了一些有待解決的開放性問題。
