基于独立集的区域涂色方式计数方法
提供四种不同颜色的颜料给图中六个区域涂色，要求每个区域涂一种颜色，有公共边的两个区域不能涂相同的颜色，则不同的涂色方法共有（）种。
常规思路
首先， $D,E,F$显然无法同色，对这三个区域有 $A_4^3$ 种涂法。 当 $B,D$ 同色时，区域被分成 $\{A\},\{B,D\},\{C\},\{E\},\{F\}$四块，有 $A_4^3 \times 2 \times 3 = 144$ 种方案。 $B,F$ 同色与 $B,D$ 同色相对称，也有 $144$ 种方案。 最后， $B,D,F$ 之间均不同色时，有 $A _4 ^3 \times 2 \times 2 = 96$ 种方案。 故总方案数为 $144 + 144 + 96 = 384$ 种。
基于独立集的思路
理论
可将A~F抽象为图中的节点，用边连接具有公共边的色块对应的节点，形成图$C_1$:
将每个节点和与之相连的节点分离，和与之不相连的节点相连（即构建 $C_1$ 的独立集），形成图$C_2$：
此时，$C_2$ 中的边所连接的节点对应的，就是“一对不具有公共边的色块”，也就是一对可以被涂上同种颜色的色块。
那么，对于 $C_2$ 中的任意子图，如果其任意两个顶点间都有相邻的边，该子图对应的所有色块都可以被同种颜色涂色。
这样的子图在图论中被称为“团”。
方便起见，本文将用团的点集表示团，如 $\{A,C,E\}$ 表示由 $A,C,E$ 三个节点组成的团。
再将$m$种颜色分配给$i$个团，方案数为 $A_m^i$ 。
若将 $C_2$ 拆分为$i$个团的方案数为 $n_i$ ，提供的最大颜色数为 $m$，总染色方案数为 $N$ ，有：
$$N = \sum_{i = 1}^{m}({n_i} \times {A_m^i})$$
实现
由于对任意节点，其参与形成的不同的团不会处于同一分割方式中，可递归地对图进行分割。
如，$A$ 节点可形成 $\{A\},\{A,C\},\{A,E\},\{A,F\},\{A,C,E\}$几个团。
以分割 $\{A\}$ 为例。此时，除$\{A\}$以外的部分形成了一张新的子图 $C_3$：
选择 $C_3$ 中的节点分类讨论，最终递归地统计每种分割方案产生的团的数量，即可得到表达式中的 $n_i$。 但在实际计算过程中，这种繁琐的递归不仅效率及其低下，也很容易出错。因此，对其进行优化是有必要的。
一种优化思路
分割时常常会遇到一类链状的图，如例题中的$C_3$。在图论中，这类图被称为路径图，含 $n$ 个节点的路径图就用 $P_n$ 表示。
这类路径图的节点排列方式各有不同，但具有相同的结构，也就有相同的分割方式与涂色方案。
定义 $f(i,k)$ 为“将路径图 $P_k$ 分割为$i$个团的方案数"。考虑到路径图的团至多有2个节点，至少有1个节点， $f(i,k) \neq 0$ 时有 $i \in [ {\lceil \frac{k}{2} \rceil},k ]$ 。
显然有 $f(k,k) = 1$ 。
若将任意两相邻节点合并为新的团，则有 $C_{k-1}^1 = k-1$ 种方案，即 $f(k-1,k) = k-1$ 。
$i < 3$ 且 $n < 4$时，路径图较为简单， $f(i,k)$ 的值小，可直接数出。见下表：
| $n$ | $f(i,n)$ |
|---|---|
| 1 | $f(1,1) = 1$ |
| 2 | $f(1,2) = 1,f(2,2) = 1$ |
| 3 | $f(1,3) = 1,f(2,3) = 2$ |
对于 $ i \geq 3 $ 或 $ n \geq 4$ 的路径图，可以在端点处递归分割，即 $f(i,k) = f(i-1,k-1) + f(i-1,k-2)$ 。
回到例题，显然 $C_3$ 属于路径图 $P_5$ 。对于 $C_3$ ，$i \in [2,3]$ , $f(2,5) = 0$ ， $f(3,5) = f(2,4) + f(2,3) = 1 + 2 = 3$ 。即将 $C_2$分割为3个团的方案有0个，分割为4个团的方案有3个。
用相同方法处理剩下四种情况，即可得：
$$N = A_4^3 \times (0+0+1+1+2) + A_4^4 \times (3+2+3+3+1) = 384$$