表題番号：2000A-094 日付：2002/02/25
研究課題グラフのゲーム彩色数
研究者所属（当時） 資格 氏名
（代表者） 教育学部 教授 鈴木　晋一
研究成果概要
　1991年に、H.L.Bodlaenderは、有限単純グラフG＝（V,E）に対して、「ゲーム彩色」と呼ばれるある制限付きの彩色を導入し、ゲーム彩色数を定義し、そのごく基本的な性質を幾つか証明した。その後何人かの研究者がこれを取り上げているが、ゲーム彩色に関する論文はまだ10編に満たない。
　本研究では、まず通常のグラフ彩色数との比較のもとに、ゲーム彩色数に関する基本的な性質を幾つか証明した。また、通常の彩色数と同じように、ゲーム彩色数の決定に際しては有効なアルゴリズムが存在しないため、ゲーム彩色数が確定した例が極めて少ないため、完全ｋ部グラフのかなり広いクラスについて、そのゲーム彩色数の決定作業を行った。
　このような作業の途中で、このゲーム彩色には数学的には面白くない欠点があることに気付き、新たに「オセロゲーム彩色」なる概念を導入した。これは通常の彩色に近く、近似値を求める計算アルゴリズムも容易に構成できて、ゲーム彩色数よりもはるかに計算が容易である。通常の彩色、ゲーム彩色およびオセロゲーム彩色の比較をしながら、その基本的な性質を調べ、その特徴付けを行ってきたが、まだ多くの課題が残っている。これまでの成果は、一応日本語の論文にまとめたが、抱えている課題の幾つかが解決したある段階で英文の論文にして公表の予定である。
　また、グラフ理論では自然なことであるが、頂点彩色を辺彩色の問題に置き換えた研究も少しずつ進んでいる。