四色方柱问题
 |
四色方柱问题是由有四個顏色的立方体組成的問題。由四色（通常是红色，蓝色，绿色和白色）將立方體着色，用四个立方体组成方柱。问题是如何将这些立方体排成一列，使得排成的长方体的每一側(前、后、左、右)都有四种颜色。
四色方柱问题可以转化为图着色问题来解决。
解法
[编辑]
希望通过给定的四个立方体，构造一张图，并通过解决图着色问题得到排列方式。图的构造方式如下：
- 图最初由4个点构成，四个点的颜色与四色方柱的四种颜色相同（红绿蓝黄）。
- 对每个立方体，考虑三个对立面，将每个对立面对应颜色的点用边连起来。本例中，对于立方体1，在图中加入了三条边：红-红、红-绿、黄-蓝。
- 根据立方体来给边着色，相同立方体对应的边染上相同颜色，不同立方体对应边染上不同颜色。本例中，分别给四个立方体对应边染上黑、青、橙、紫四种颜色。
下一步需要在构成的无向图中找出两个特殊子图，一个图表示叠置长方体的前后两面，另一个表示左右两面。为了区分叠置的立方体的前/左面与后/右面，需要给两个子图设定方向，使得每个顶点恰好有一个入度和一个出度。
构建的子图应满足以下三个性质：
- 两个子图没有共同边。否则某个立方体的一对面既是前后两面，又是左右两面。
- 每个子图包含仅包含每个立方体的一条边。因为每条边只能表示一个立方体，而既要用上所有立方体，又不能重复使用。
- 子图中每个顶点的度为2。因为每个子图表示长方体的一对面，每种颜色需要在这一对面中出现两次。
找到两个子图之后，根据构建的两个有向子图确定对应立方体每个面的颜色。
例如，在本例中，规定有向边的起点对应立方体的前/左面，有向边的终点对应立方体的后/右面。
那么四个立方体前面的颜色分别是：黄，绿，蓝，红；左面的颜色分别是：红，蓝，黄，绿。