四色方柱問題
 |
四色方柱問題是由有四個顏色的立方體組成的問題。由四色（通常是紅色，藍色，綠色和白色）將立方體著色，用四個立方體組成方柱。問題是如何將這些立方體排成一列，使得排成的長方體的每一側(前、後、左、右)都有四種顏色。
四色方柱問題可以轉化為圖著色問題來解決。
解法
[編輯]
希望通過給定的四個立方體，構造一張圖，並通過解決圖著色問題得到排列方式。圖的構造方式如下：
- 圖最初由4個點構成，四個點的顏色與四色方柱的四種顏色相同（紅綠藍黃）。
- 對每個立方體，考慮三個對立面，將每個對立面對應顏色的點用邊連起來。本例中，對於立方體1，在圖中加入了三條邊：紅-紅、紅-綠、黃-藍。
- 根據立方體來給邊著色，相同立方體對應的邊染上相同顏色，不同立方體對應邊染上不同顏色。本例中，分別給四個立方體對應邊染上黑、青、橙、紫四種顏色。
下一步需要在構成的無向圖中找出兩個特殊子圖，一個圖表示疊置長方體的前後兩面，另一個表示左右兩面。為了區分疊置的立方體的前/左面與後/右面，需要給兩個子圖設定方向，使得每個頂點恰好有一個入度和一個出度。
構建的子圖應滿足以下三個性質：
- 兩個子圖沒有共同邊。否則某個立方體的一對面既是前後兩面，又是左右兩面。
- 每個子圖包含僅包含每個立方體的一條邊。因為每條邊只能表示一個立方體，而既要用上所有立方體，又不能重複使用。
- 子圖中每個頂點的度為2。因為每個子圖表示長方體的一對面，每種顏色需要在這一對面中出現兩次。
找到兩個子圖之後，根據構建的兩個有向子圖確定對應立方體每個面的顏色。
例如，在本例中，規定有向邊的起點對應立方體的前/左面，有向邊的終點對應立方體的後/右面。
那麼四個立方體前面的顏色分別是：黃，綠，藍，紅；左面的顏色分別是：紅，藍，黃，綠。