关于禁止bull和H子图的图的k-可着色性研究及其在图着色理论中的意义

《Discrete Mathematics》：On k-colorability of ( bull, H)-free graphs

这篇综述聚焦于(bull, H)-free图的k-可着色性研究。三着色问题在图论中是一个NP-完全问题。本文首先对k≥3的情形，刻画了所有包含长度至少为6的诱导环的k-可着色(bull, claw)-free图。更重要的是，作者首次给出了所有非4-可着色连通(bull, claw)-free图、(bull, chair, C5)-free图以及所有非5-可着色连通(bull, claw, C5)-free图的完整特征。这些结果深化了我们对特定图类着色复杂性的理解，并为相关着色算法的设计提供了理论基础。

　　

摘要

3-可着色问题是著名的NP-完全问题，并且对于bull-free图（其中bull图是由一个K₃在其两个顶点上各连接一条悬挂边构成的图）而言，该问题依然是NP-完全的。在本文中，对于k≥3，我们刻画了所有包含长度至少为6的诱导环的k-可着色(bull, claw)-free图。此外，我们提出了所有非4-可着色连通(bull, claw)-free图和(bull, chair, C₅)-free图，以及所有非5-可着色连通(bull, claw, C₅)-free图的完整刻画。

引言

我们考虑有限、简单、无向图。对于未在此定义的术语和符号，我们参考[2]。

图G的一个诱导子图是由顶点集S?V(G)诱导的子图，其中两个顶点相邻当且仅当它们在G中相邻。特别地，我们说该子图由S诱导。如果图H与G的某个诱导子图同构，我们也称H是G的一个诱导子图。

给定一个图族H和一个图G，如果G不包含H中的任何图作为诱导子图，则称G是H-free的。在这种语境下，H中的图被称为禁止诱导子图。

图G的一个顶点着色是真着色，如果相邻顶点获得不同的颜色。如果图G可以用k种颜色进行真着色，则称其为k-可着色的。使得图G是k-可着色（chromatic number）的最小整数k称为G的色数，记作χ(G)。显然，对任意图G，χ(G)≥ω(G)，其中ω(G)表示G的团数，即G中最大完全子图的阶数。此外，如果对G的每个诱导子图G'都有χ(G') = ω(G')，则图G是完美的。对于子图H和顶点v，令d_H(v)=|N(v)∩V(H)|。

对于一个长度p≥3的诱导环C_p，令C_p[k₁, k₂, …, k_p]表示一个诱导环C_p的团扩张，其中它的顶点v₁, v₂, …, v_p分别被完全图K_ki所替换（对于1≤i≤p），并且相邻团之间的所有顶点对都有一条边相连（见图1）。我们用G⊕H表示一个顶点集为V(G)∪V(H)、边集为E(G)∪E(H)∪{vw: v∈V(G), w∈V(H)}的图。

设G是一个环C_n的团扩张C[k₁, …, k_n]，且k∈N。让我们用数字1, …, k₁标记第一个团的顶点，用数字k₁+1, …, k₁+k₂标记第二个团的顶点，依此类推。那么，环形k-着色算法，也称为k-CC算法，是一个为G的第m个顶点分配颜色((m-1) mod k) + 1（对于m = 1, …, k₁+…+k_n）的算法。

由五个顶点v₁, v₂, v₃, v₄, v₅及边v₁v₂, v₂v₃, v₃v₄, v₄v₅, v₂v₄构成的图称为一个bull。令S_i,j,k表示一个三条边分别被细分i-1、j-1和k-1次的3-星。图S_1,1,1被称为一个爪（claw），而S_1,1,2被称为一个椅子（chair）。

图G的独立数（independence number） α(G)是最大的k∈N，使得存在S?V(G)，满足|S|=k且S是一个独立顶点集。

3-可着色问题对于claw-free图和K₃-free图也是NP-完全的（参见[7]），因此对于bull-free图也是NP-完全的。在过去二十年中，关于禁止子图着色的结果大量涌现（参见[3]、[4]、[5]、[10]、[11]、[14]、[15]，以及参见[7]、[12]、[13]的三篇综述）。关于chair-free图结构的进一步讨论可以在[16]中找到。

我们的研究受到[5]的启发，并且使用了其中的一些定义和符号。特别地，我们将一个非3-可着色图C_2n+1⊕K₁称为一个奇数轮（odd wheel） W_2n+1。一个阶数为3p+1（p≥1）的图G，如果它包含一个环C: u₀u₁…u_3pu₀，其中对于每个i∈[p]有 {u_3i-2, u_3i-1, u_3i+1, u_3i+2} = N_G(u_3i) 且 {u_3i-3, u_3i} = N_G(u_3i-1) ∩ N_G(u_3i-2)，其中[p]:={1,2,…,p}，则称G为一个纺锤图（spindle graph） M_3p+1。注意到M₄?K₄且M₇就是著名的Moser纺锤。

命题 1 [5]

对于每个p≥1，图M_3p+1都不是3-可着色的。

由于3-可着色问题对于claw-free图和K₃-free图是NP-完全的（参见[7]），因此对于bull-free图也是NP-完全的。以下[5]和[9]中的定理激发了我们的研究。

定理 2 [5]

设G是一个连通(bull, claw)-free图。则下列情况之一成立：

(i) G包含W₅，或

(ii) G包含一个纺锤图M_3i+1（对于某个i≥1），或

(iii) G是3-可着色的。

定理 3 [9]

设G是一个连通(bull, chair)-free图。则

(i) G包含一个奇数轮，或

(ii) G包含一个纺锤图M_3i+1（对于某个i≥1），或

(iii) G是3-可着色的。

本文的目标是研究(bull, H)-free图的k-可着色性。对于k≥4，我们将不失一般性地假设δ(G)≥4，否则可以通过移除度数小于4的顶点来简化G（其着色是平凡的）。以下是我们的主要结果。第一个定理为任何奇数环的团扩张是k-可着色的提供了必要和充分条件。

定理 4

令n≥1，k≥3，且G是一个团扩张C_2n+1[k₁, …, k_2n+1]。则G是k-可着色的当且仅当满足以下两个条件（所有下标均对k取模）：

(i) ?i∈[2n+1]，有 k_i+ k_i+1≤ k；

(ii) ∑_i=1²ⁿ⁺¹k_i≤ nk。

利用定理10和定理11，我们可以观察到定理4的一个简单推论。

推论 5

设G是一个包含长度p≥7的诱导环的连通(bull, claw)-free图。如果α(G)≥3，那么G是k-可着色的，或者G包含K_k+1，或者G是一个满足存在i∈[p]使得k_i+k_i+1> k 或 ∑_i=1^pk_i> nk（其中所有下标模k）的团扩张C_p[k₁, …, k_p]。

接下来，我们得到了所有非4-可着色连通(bull, claw)-free图，以及所有非4-可着色连通(bull, chair, C₅)-free图的完整刻画。

定理 6

设G是一个连通(bull, claw)-free图，且i≥1。则

(i) G包含C?₇⊕K₁，或

(ii) G包含C₅⊕K₂，或

(iii) G包含M₄⊕K₁或 M₇⊕K₁，或

(iv) G包含C_2i+1[2,2,…,2,1,3,1,3,…,1] 或 C_2i+1[2,2,…,2,1]，或

(v) G包含一个诱导环C₅且 |V(G)| > 8，或

(vi) G是4-可着色的。

定理 7

设G是一个连通(bull, chair, C₅)-free图，且i≥1。则

(i) G包含C?₇⊕K₁，或

(ii) G包含C_2i+1⊕K₂，或

(iii) G包含M_3i+1⊕K₁，或

(iv) G包含C_2i+1[2,2,…,2,1,3,1,3,…,1] 或 C_2i+1[2,2,…,2,1]，或

(v) G是4-可着色的。

最后，我们提出了所有非5-可着色连通(bull, claw, C₅)-free图的完整刻画。

定理 8

设G是一个连通(bull, claw, C₅)-free图。则

(i) G包含K₆，或

(ii) G包含C?₇⊕K₂，或

(iii) G包含C?₉⊕K₁，或

(iv) α(G)=2 且 |V(G)| ≥ 11，或

(v) α(G)=2 且 Δ(G) ≥ 9，或

(vi) G是一个满足 ∑_i=1²ⁿ⁺¹k_i- 5n > 0 的团扩张C_2n+1[k₁, …, k_2n+1]，或

(vii) G是5-可着色的。