この写真で驚くべきことは何ですか？
実際、それはユニークです。 17 x 17マトリックスは4色で塗りつぶされており、1つの（！）四角形を作成して、そのすべての角を同じ色にすることはできません。 これは、
x軸と
y軸に平行な異なるポイントとエッジに頂点を持つ任意のサイズの長方形を指します。
比較のために、セルの色を置き換えると、すぐに多くの単色の長方形が表示されます。 たとえば、左上のセルの色が青から赤に変更された場合。
同様に、1つのランダムなセルを中央から変更した場合。
コンビナトリアル分析の分野からのこの問題は、2009年11月20日にクレイ数学研究所のWilliam Gasarchによって
提起されました。彼は以前にマトリックスの着色に関する基本的な
研究を発表し、多色長方形なしの4色でほぼすべてのサイズのマトリックスの着色または非着色を証明しました。 彼の
テーブルには、17x17、18x18、および12X21のいくつかのサイズしか不明のままでした。
フライベルクマイニングアカデミー（ドイツ）のコンピューターサイエンス研究所の数学者ブランドシュタインバッハ、および西インド諸島（トリニダードトバゴ）のコンピューターおよび情報技術学部の元従業員であるクリスチャンポストホフは、カウント17x17を4
色で
管理しました単一の単色の長方形なしの色！ さらに、18x18マトリックスの色付けもできました。 したがって、現在未解決の形式は21x12のみです。
「最も複雑な4色の四角形のないグリッド-オープンな多値問題の解決」およびSteinbach-Posthoffアルゴリズムの結果は、2012年5月14日にビクトリアで開催される国際シンポジウムで公開されます。 （カナダ）。
グラフの色付けは
実用上非常に重要であり、スケジューリング、マイクロプロセッサでのレジスタ割り当て、実行可能コードのキャッシュ配布、チャネルスループットを最大化して干渉を最小限に抑える無線周波数配布、数値法の並列化、微分の計算、電子透かし、クラスター分析およびその他の多くの分野。