一意彩色可能グラフにおける局所的及び大域的制約構造についての研究

点击翻译按钮获取中文摘要

本研究においては、極小な非理想グラフの有する種々の組合せ構造を明らかにしてゆく過程において、一意彩色可能なグラフの彩色構造を局所的、大域的にうまく特徴付けることを目指して、研究を進めて参ります。本年も昨年と同様、「circularなPartitionable Graph」に関するGrinstead'sConjectureという難予想に取組み、その解決へ向けて様々な角度から研究を進めて参りました。これまではクリーク数が5以下の比較的自明な場合にその成立が確かめられたに過ぎず、予想が一般に成立する可能性は低いものと考えられていました。本年の成果としては、このGrinstedの予想に関して、この予想が成立するクリーク数の上限を、computational proofを駆使して一気に15にまで押し上げることに成功しております。現在までの成果は、"Grinstead's Conjecture is true for some fixed $\omega(G)$'s"というタイトルで「The 3rd Hungarian-Japanese Symposium 2003」において発表し、同タイトル「Grinstead's Conjecture is true for some fixed $\omega(G)$'s.」の論文は、上記コンファレンスのプロシーディングス集にRefereed Paperとして受理されています。現在Discrete Mathematicsに、これを発展させた論文を投稿しています。理論ベースのapproachとしては、組合せ論的グラフ理論、整数計画法、位相幾何学的グラフ理論の3つの視点を柱とする研究を進めていきました。その際必要となる論文誌や書籍の購入費用、および上述致しました国際シンポジウムや国内の学会での発表に要する費用を適宜、申請致しました通り、使用させて頂きました。また、計算機シュミレーションによる反例の探索と、computationalproofの実装に要する計算機環境の整備に必要な範囲で、申請致しました通り、適切な計算機周りの消耗品を購入致しました。