图的分数着色与分数团 1. 基本概念与动机 图的分数着色是经典顶点着色问题的推广。在经典着色中，每个顶点被分配一种颜色，相邻顶点颜色不同，目标是使用最少颜色数（色数χ(G)）。分数着色允许将多个颜色"分配给"每个顶点，且相邻顶点分配的颜色集合不相交。其核心动机是提供更精细的图参数，尤其在组合优化和算法设计中能提供更紧的界。 2. 分数着色的定义 分数色数χ_ f(G)可通过线性规划或独立集加权和定义。常用定义基于"b-重着色"：对整数b≥1，若每个顶点被分配一个大小为b的颜色子集，且相邻顶点的颜色子集不相交，则称为b-重着色。分数色数χ_ f(G) = inf{ a/b | 存在a种颜色的b-重着色 }。等价地，χ_ f(G)是独立集覆盖顶点集所需的最小权重和，其中每个独立集的权重非负，且每个顶点被覆盖的总权重至少为1。 3. 分数团与分数团数 分数团数ω_ f(G)是分数着色的对偶概念。定义为最大权重和，使得每个顶点被分配一个权重（0≤w(v)≤1），且每个团的权重和不超过1。分数团数满足ω(G) ≤ ω_ f(G) ≤ χ_ f(G) ≤ χ(G)，其中ω(G)是经典团数。 4. 分数着色与图乘积 分数色数具有乘积性质：χ_ f(G × H) = χ_ f(G) χ_ f(H)，其中×是图张量积。这一性质是分数着色区别于经典着色的关键特征，经典色数不满足类似等式。 5. 分数着色与线性规划 分数色数可通过线性规划计算：最小化∑ I x_ I（对所有独立集I），满足∑ {I∋v} x_ I ≥ 1对每个顶点v，且x_ I ≥ 0。对偶问题是分数团数的线性规划表示。分数色数与整数规划松弛密切相关，为近似算法提供理论依据。 6. 分数着色的应用 分数着色在调度问题、资源分配和通信网络中用于建模冲突避免。例如，在无线信道分配中，分数着色能更灵活地处理多信道共享。此外，它是研究图色数极限行为的重要工具，如完美图的分数色数等于团数。 7. 分数着色的计算复杂性 计算χ_ f(G)是NP-难问题，但可通过椭球法在多项式时间内近似到任意精度，因为对应的线性规划规模虽指数级，但存在多项式时间分离预言。实际中常使用迭代算法或基于图结构的启发式方法。