d-非正常色数的谱方法：Hoffman型等号刻画与强乘积G?Kd+1的色数关系

《European Journal of Combinatorics》：Spectral approaches for d-improper chromatic number

　　

本文探讨d-非正常（d-improper）与t-聚类（t-clustered）染色的代数方法，其中染色约束被放松以允许出现单色边。Bilu（J. Comb. Theory Ser. B, 96(4):608–613, 2006）证明了d-非正常染色情形下Hoffman界的一个推广。研究人员通过刻画等号情形强化了该定理。特别地，若Hoffman界对图G取紧，则d-非正常Hoffman界对强乘积G?K_d+1取紧。此外，研究人员证明了Cvetkovi?惯性界（inertia bound）以及Elphick和Wocjan的多特征值下界（multi-eigenvalue lower bounds）的d-非正常类比。研究人员猜测图G的色数（chromatic number）与其与完全图K_d+1的强乘积G?K_d+1的d-非正常色数（d-improper chromatic number）相等，并在特殊图类中证明该猜想，包括完美图（perfect graphs）和色数至多为4的图。进一步，研究人员证明了该等式的分数类比（fractional analogue）、聚类类比（clustered analogue）以及若干谱松弛（spectral relaxations）。

研究背景方面，d-非正常染色（d-improper colouring，允许每个顶点至多d个同色邻点）与t-聚类染色（t-clustered colouring，每个单色连通分量至多t个顶点）均为正常染色的自然松弛，允许受控的单色边。原文指出，此类染色出现在ad hoc无线电通信网络、电路设计和分布式算法等应用背景中，并在结构图论、概率/极值图论中得到研究。与正常染色不同，d-非正常与t-聚类染色不易由到目标图的图同态存在性描述，因此一些标准染色技术难以直接适配；同时色数计算困难，需要利用度、特征值等较易计算的图不变量建立界。原文还提到，对对称图中独立集对应概念的兴趣、Huang对敏感性猜想的解决以及Esperet和Wood对某些强乘积染色的处理，促使系统探索d-非正常与聚类染色的代数方法。研究人员因此开展谱图论与代数组合研究，推广Hoffman界、惯性界和多特征值下界，刻画等号情形，并提出χ(G)=χ_d(G?K_d+1)的猜想，证明分数形式、聚类形式及若干特殊图类中的情形。其意义在于把d-非正常与t-聚类染色纳入谱图论框架，给出强乘积、分数染色与聚类染色之间的系统联系。

关键技术方法（不超过250字）：本研究为纯理论图论研究，不涉及试剂、培养、质粒构建或样本队列。研究人员利用邻接矩阵、Laplacian矩阵与signless Laplacian矩阵的谱，结合Perron–Frobenius定理、Cauchy交错定理、商矩阵、权正规划分与谱分解，建立d-非正常Hoffman型等号刻画；通过强乘积G?K_d+1、b重染色（b-fold colouring）、分数染色、字典积（lexicographic product）以及辅助图I_G,c的循环消去与裁剪构造，证明聚类与分数类比和相关谱松弛。

研究结果按原文小标题概括如下。1. Introduction：引入d-非正常与t-聚类染色，回顾Bilu的d-非正常Hoffman界，提出核心猜想χ(G)=χ_d(G?K_d+1)，并列出χ≤4、完美图、谱界取等等支持情形及分数、聚类弱形式。1.1. Definitions：形式定义d-非正常色数χ_d(G)、t-聚类色数χ_t?(G)、b重与分数版本，说明χ₀(G)=χ(G)，并给出χ_d(G)≥ω(G)/(d+1)及Lovász上界χ_d(G)≤(Δ(G)+1)/(d+1)。2. Preliminary observations：Lemma 3建立χ(G)≥χ_d+1?(G?K_d+1)≥χ_d(G?K_d+1)≥χ(G?K_d+1)/(d+1)=χ_d+1(G)/(d+1)≥χ_f(G)的链；Lemma 4给出b重版本；Theorem 5证明分数类比χ_f^d(G?K_d+1)=χ_f(G)；Theorem 6给出聚类分数类比；Lemma 7、8联系b重染色与强乘积；Lemma 9证明字典积G[H]的t-聚类色数在t≥|V(H)|时只依赖G与H顶点数。2.1. Tools from spectral graph theory：介绍Perron–Frobenius定理、特征值交错、Cauchy交错定理、商矩阵、权正规划分与谱分解等工具。3. Spectral bounds for the d-improper chromatic number：目标是推广基于特征值的色数下界。3.1. d-improper Hoffman colourings：Theorem 16重述并强化Bilu界χ_d(G)≥(λ₁?λ_n)/(d?λ_n)，并刻画等号情形：λ_n重数至少m?1；连通时各色类d-正则且划分为权正规；λ_n重数恰为m?1时Hoffman染色唯一；正则图中每个顶点在本色类有d个邻点、在其他色类有d?λ_n个邻点。Lemma 17证明若G有Hoffman染色，则G?K_d+1有d-非正常Hoffman染色；Corollary 18给出聚类Hoffman版本，并以Paley(9)线图等说明聚类Hoffman染色图不一定是强乘积。3.2. Other spectral bounds：Theorem 19给出d-非正常惯性界α_d(G)≤min{n?n_d⁺(A), n?n_d^?(A)}；Corollary 20得到χ_d(G)≥max{n/(n?n_d⁺(A)), n/(n?n_d^?(A))}；Theorem 21给出四个多特征值下界，m=1时分别退化为d-非正常Hoffman界及Nikiforov、Kolotilina型界的d-非正常版本。4. The d-improper chromatic number of G?K_d+1：围绕猜想χ(G)=χ_d(G?K_d+1)，指出只需证反向不等式；d=0平凡，d=1由聚类版本得到；Theorem 22用Buys的论证证明χ(G)≤4（含平面图）时猜想成立；通过比较d-非正常谱界与χ(G)的谱界，证明Hoffman可染色图、满足χ(G)=ω(G)的图（特别完美图）以及Nikiforov、Kolotilina界取紧等情形成立。4.1. The t-clustered chromatic numbers of G?K_t：Theorem 25证明χ_??(G)=χ_?t?(G?K_t)；Corollary 26取?=1得χ(G)=χ_t?(G?K_t)；Corollary 27给出b重类比χ_b(G)=χ_bt?(G?K_t)；Corollary 28给出字典积版本χ_??(G)=χ_?t?(G[H])。

讨论与结论部分可概括为：该研究系统建立了d-非正常与t-聚类染色的谱界、等号刻画及强乘积关系，证明分数版本χ_f^d(G?K_d+1)=χ_f(G)和聚类版本χ(G)=χ_t?(G?K_t)等结论，为 improper 与 clustered 染色提供代数框架。原文“Note added”指出，在较早版本上传至arXiv后，猜想2在社区中迅速传播；Norin和Steiner随后证明，尽管该猜想至多相差一个因子2是正确的，但该猜想为假。该后记是对核心整值猜想最终状态的明确结论性说明。