未解決の問題
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/06/28 15:48 UTC 版)
単位距離だけ離れている任意の2つの点が同じ色にならないように平面を彩色する問題 (Hadwiger–Nelson problem) は未解決だが、その彩色数は5、6、7のいずれかだということまでは判明している。その他のグラフの彩色数に関する未解決問題としては、Hadwiger予想(en)がある。これは、彩色数 k のグラフはマイナーとして頂点 k 個の完全グラフを含む、という予想である。また、Erdős–Faber–Lovász予想(en)は、k-クリークが互いに高々1つの頂点を共有する形でk個連結されたグラフはk-彩色的だ、というものである。Albertson予想(en)は、k-彩色的グラフの中で完全グラフが最も交差数が小さい、というものである。 BirkhoffとLewisは四色問題を攻略する手段として彩色多項式を導入し、平面グラフ G の彩色多項式 P ( G , t ) {\displaystyle P(G,t)} は [ 4 , ∞ ) {\displaystyle [4,\infty )} の領域でゼロにならないという予想を立てた。そのような彩色多項式が [ 5 , ∞ ) {\displaystyle [5,\infty )} の領域でゼロにならないことと、 P ( G , 4 ) ≠ 0 {\displaystyle P(G,4)\neq 0} であることは判明しているが、彼らの予想自体は未解決である。任意の2つのグラフの彩色多項式が同一かどうかの判定や、ある多項式が彩色多項式かどうかの判定も未解決の問題である。
※この「未解決の問題」の解説は、「グラフ彩色」の解説の一部です。
「未解決の問題」を含む「グラフ彩色」の記事については、「グラフ彩色」の概要を参照ください。
「未解決の問題」の例文・使い方・用例・文例
- 未解決の問題のページへのリンク
