この記事のポイント

  • 四色問題が解決されてから2026年で50年になる
  • 国立情報学研究所や東京大学などの国際研究グループが、塗り分け計算を高速化する新たな手法を開発した
  • 2026年3月の論文では、頂点数nの平面グラフをO(n log n)時間で4色に塗り分ける手法を示した
  • 2026年10月29日の続報では、O(n)時間の線形時間アルゴリズムを示し、最適だとしている
  • 新しい証明では8202通りの配置をコンピューターで検証した
目次
  1. 50年の節目に新たな手法
  2. 四色問題とは何か
  3. O(n log n)からO(n)へ
  4. 半導体設計への応用も
  5. 検証はコンピューターで
01

50年の節目に新たな手法

世界は4色で塗り分けられる。どんな地図も4色あれば対応できるとした数学の難問「四色問題」が解決されてから2026年で50年になる。この節目に国立情報学研究所(NII)や東京大学などの国際研究グループは、塗り分け計算を高速化する新たな手法を開発したと日経は伝えた。

研究グループは、東京大学の井上裕太氏、国立情報学研究所の河原林健一氏、東京大学の宮下淳之氏、カナダのサイモンフレーザー大学のボヤン・モハール氏、デンマーク工科大学のカーステン・トマセン氏、コペンハーゲン大学のミッケル・ソーラップ氏の6人だ。論文は2026年3月に発表され、11月に開かれた計算機科学の国際会議FOCS 2026で報告されたと、クアンタ・マガジンは伝えた。

02

四色問題とは何か

四色問題は、1852年にフランシス・ガスリーがイギリスの州の地図を塗っていて気づいた問いだ。隣り合う地域同士が同じ色にならないよう、地図を4色で塗り分けられるかという問題で、数学者を100年以上悩ませてきたと日経は伝えた。

1976年にケネス・アッペルとウォルフガング・ハーケンが、コンピューターを使って証明した。1997年にはロバートソンらが証明を簡略化し、検証する配置を633通りに減らした。だが、実際に地図を4色に塗り分ける計算は、頂点数nに対してnの2乗の時間(O(n²))がかかり、30年間改善されなかったとクアンタ・マガジンは伝えた。

03

O(n log n)からO(n)へ

新しい手法の鍵は、一度にたくさんの場所を処理することだ。従来は、塗り分けを簡単にする配置を一つずつ探しては取り除く方法だった。新しい証明では、平面グラフの中に、互いに干渉しない「削減可能な配置」が直線的にたくさんあることを示した。これにより、計算量はO(n log n)まで下がったとクアンタ・マガジンは伝えた。

2026年10月29日には、同じ6人が続報を発表した。塗り分けを線形時間、つまりO(n)時間で行う手法を示し、最適だとしている。グラフを読み込んでn個の頂点に色を付けるだけでも線形時間は必要で、これ以上の高速化はできないと、研究を解説したダニルチェンコ氏の記事は伝えている。

04

半導体設計への応用も

塗り分けの高速化は、半導体の設計などへの応用も見込まれると日経は伝えた。地図の塗り分けは、グラフの彩色という問題に帰着する。グラフの彩色は、回路設計などの割り当て問題にも応用される考え方だ。

ただ、今回の成果は理論の段階だ。線形時間の論文は査読前のプレプリントで、実装や計測の報告はないと、解説記事は指摘している。定数因子がどれほど大きいかは分かっておらず、実用への道のりはこれからだ。

05

検証はコンピューターで

新しい証明も、コンピューターによる検証に頼っている。8202通りの配置をコンピューターで検証した。1976年の証明では約1500通り、1997年の証明では633通りだった。検証する配置の数は増えたが、一度に多くの配置を処理できるようになったとクアンタ・マガジンは伝えた。

研究グループは、検証用のコードを公開している。2026年6月には、ジェミニやクロード・コード、コーデックスが独立に書いたコードでも、検証が再現されることが示されたと解説記事は伝えた。次の焦点は、線形時間の論文が査読を経て認められるかどうかと、平面グラフ以外の曲面への応用が進むかどうかだ。

出典・参考資料