图的分数染色 分数染色是图论中经典顶点着色问题的自然推广。在传统顶点着色中，每个顶点被分配一种颜色，相邻顶点颜色必须不同。分数染色则允许给每个顶点分配一个颜色集合，通过放宽约束条件来研究更精细的染色性质。 基本定义与模型构建 分数染色的标准定义通过"b-重染色"模型建立：对任意正整数b，图G的b-重染色是将颜色集{1,2,...,a}的b-元素子集分配给每个顶点，使得相邻顶点获得的颜色子集不相交。分数色数χ_ f(G)定义为inf{a/b : 存在G的b-重染色}。这个定义可以等价地表述为顶点集到幂集的映射，要求相邻顶点的像集不相交。 线性规划刻画 分数染色最有力的研究工具是线性规划方法。考虑所有独立集I构成的集合族，定义变量x_ I表示独立集I在染色方案中的使用程度。分数色数等价于以下线性规划的最优值：最小化∑x_ I，满足对每个顶点v，∑{I∋v} x_ I ≥ 1，且x_ I ≥ 0。这个线性规划的对偶问题是最大独立集权值和，满足每个顶点在独立集中的总权重不超过1。 分数团数 与分数染色对偶的概念是分数团数ω_ f(G)。分数团是给每个顶点分配非负权重，使得每个独立集的顶点权重和不超过1。分数团数定义为顶点权重和的最大值。由线性规划对偶定理，对任意图G都有χ_ f(G) = ω_ f(G)。这个等式建立了分数染色与分数团之间的完美对偶关系。 分数染色的性质 分数色数具有多个重要性质：它是整数色数的下界χ_ f(G) ≤ χ(G)；是团数的上界ω(G) ≤ χ_ f(G)；满足次可加性χ_ f(G∪H) ≤ χ_ f(G) + χ_ f(H)；在积图运算下满足χ_ f(G×H) = max{χ_ f(G), χ_ f(H)}。这些性质使得分数色数成为研究图染色问题的精细工具。 Kneser图的分数染色 Kneser图KG(n,k)的分数染色有特别优美的解。通过给每个顶点分配均匀权重1/⌊n/k⌋，可以证明χ_ f(KG(n,k)) = n/k。这个结果推广了经典的Kneser图染色定理，展示了分数染色在处理极值组合问题中的优势。 分数染色的计算复杂性 尽管分数色数定义为有理数，但已知它总是有理数，且分子分母不超过顶点数。计算分数色数是NP难的，但对于完美图等特殊图类存在多项式时间算法。近似算法方面，可以通过椭球法求解线性规划来获得任意精度的近似值。 应用与推广 分数染色在信息论、调度理论、资源分配等领域有广泛应用。它还可以推广到分数边染色、分数全染色等变体，以及在线性系统、编码理论中的推广。分数染色的研究促进了图论与组合优化的深度融合。