图的分数染色与分数团 1. 基本定义 分数染色是经典图染色的推广。在经典顶点着色中，每个顶点被分配一种颜色，且相邻顶点颜色不同。若将颜色视为整数集合，分数染色则允许将 颜色的“份额” 分配给顶点。具体来说： 设函数 \( f: V \to 2^{\mathbb{Q}} \) 将顶点映射到有理数集合的子集（代表颜色份额）。 要求相邻顶点分配的份额集合无交集，且每个顶点的份额集合大小至少为 1（即顶点至少分到 1 个完整颜色单位）。 分数色数 \(\chi_ f(G)\) 是满足上述条件的最小总颜色数（即所有份额集合的并集大小）。 2. 分数团的定义 分数团是分数染色的对偶概念： 经典团是图中两两相邻的顶点集合，而分数团允许顶点以 权重 形式参与。 定义函数 \( w: V \to [ 0,1 ] \)，使得图中任意独立集（无边相连的顶点集）的权重和不超过 1。 分数团数 \(\omega_ f(G)\) 是满足条件的最大权重和（即 \(\max \sum_ {v \in V} w(v)\)）。 3. 线性规划模型 分数染色和分数团可通过线性规划严格定义： 分数染色数 ： \[ \chi_ f(G) = \min \sum_ {c \in C} x_ c \] 满足约束：对每个顶点 \(v\)，\(\sum_ {c \in C(v)} x_ c \geq 1\)（\(x_ c \geq 0\)，\(C\) 为颜色集）。 分数团数 ： \[ \omega_ f(G) = \max \sum_ {v \in V} y_ v \] 满足约束：对每个独立集 \(I\)，\(\sum_ {v \in I} y_ v \leq 1\)（\(y_ v \geq 0\)）。 4. 对偶关系 根据线性规划对偶定理，有： \[ \omega_ f(G) = \chi_ f(G) \] 这一等式对任意图成立，与经典图论中 \(\omega(G) \leq \chi(G)\) 的松散关系形成对比。 5. 应用与性质 计算复杂性 ：分数色数的计算是 NP-难的，但可通过椭球法在多项式时间内近似（因线性规划的多项式可解性）。 与经典参数的关系 ： \[ \omega(G) \leq \omega_ f(G) = \chi_ f(G) \leq \chi(G) \] 例如，奇环图 \(C_ 5\) 满足 \(\omega(G)=2, \chi(G)=3, \chi_ f(G)=2.5\)。 分数染色与图同态 ：分数色数可定义为图到 Kneser 图的同态的最小维数。 6. 推广与变体 分数边染色 ：类似地将颜色份额分配给边，要求相邻边无交集，分数边色数 \(\chi'_ f(G)\) 与最大匹配的权重相关。 分数全染色 ：同时考虑顶点和边的份额分配。 分数染色与分数团通过线性规划揭示了图参数的内在对称性，为经典图论问题提供了更精细的分析工具。