地図と塗り分け

平面を有限個の領域 $R_1, \ldots, R_n$（国）に分割したものを地図と呼びます。ただし各国 $R_i$ は連結な開集合とし、境界は有限本の曲線からなるものとします。2 つの国 $R_i, R_j$ が隣接するとは、両者の境界が共有部分をもち、しかもその共有部分が 1 点ではなく曲線を含むことをいいます。

写像 $c \colon \{R_1,\ldots,R_n\} \to \{1,\ldots,k\}$ が**$k$ 彩色**であるとは、隣接するどの 2 国 $R_i, R_j$ についても $c(R_i) \neq c(R_j)$ が成り立つことをいいます。