给定分解的图的色数问题

嘿，我明白你卡在这个证明上的感觉了——有时候盯着色数的不等式想直接推导或者用反证，反而会绕进死胡同。其实这个问题最直接的解法是构造一个合法的着色方案，咱们一步步来理清楚：

首先先明确一下图分解的定义：这里的“分解”指的是边不交分解，也就是图G的边集是所有Hᵢ边集的不交并，顶点集和G完全一致。

接下来是核心的构造思路：

• 第一步，给每个子图做合法着色：对于每个i∈[k]，用cᵢ种颜色给Hᵢ完成合法着色（因为χ(Hᵢ)=cᵢ，所以这样的着色方案必然存在），保证Hᵢ里相邻的顶点颜色不同。
• 第二步，给G的顶点分配组合颜色：对G中的任意顶点v，定义它的颜色为一个k元组 (col₁(v), col₂(v), ..., colₖ(v))，其中colᵢ(v)就是v在Hᵢ着色方案里的颜色。
• 第三步，验证组合着色的合法性：假设G中有一条边uv，这条边必然属于某个Hᵢ（毕竟边集是不交并）。在Hᵢ里uv是相邻顶点，所以colᵢ(u)≠colᵢ(v)，这就意味着u和v的k元组颜色至少有第i个分量不同，整个元组颜色自然也不同——完全满足G中相邻顶点颜色不同的要求。
• 最后统计颜色总数：每个分量有cᵢ种选择，总共有 c₁·c₂·…·cₖ 种不同的组合颜色，这就直接证明了G是 c₁·c₂·…·cₖ-可着色的，也就是χ(G)≤这个乘积。

其实这个思路本质是利用了着色的笛卡尔积，把每个子图的独立着色组合起来，既简单又直接，比纠结最大度或者反证法要高效得多。

备注：内容来源于stack exchange，提问作者bugrurner