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

独特可着色图中的局部和全局约束结构研究

• 批准号: 13740055
• 负责人: 佐久間 雅
• 金额: $ 1.34万
• 依托单位: The University of Tokyo
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2001
• 资助国家: 日本
• 起止时间: 2001 至 2002
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-13740055/
• 关键词: perfect graph; partitionable graph; circulant; Grinstaed's Conjecture; near-factorization; uniquely colorable graph; the Strong Perfect Graph Conjecture; circular graph (circulant); Grin stead's Conjecture

本研究においては、極小な非理想グラフの有する種々の組合せ構造を明らかにしてゆく過程において、一意彩色可能なグラフの彩色構造を局所的、大域的にうまく特徴付けることを目指して、研究を進めて参ります。本年も昨年と同様、「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の実装に要する計算機環境の整備に必要な範囲で、申請致しました通り、適切な計算機周りの消耗品を購入致しました。

在这项研究中，我们将继续进行研究，以成功地表征本地和全球独特可着色图的着色结构，以阐明极其小的非理想图的各种组合结构。与去年一样，我们一直在为“圆形分区图”的艰难预测，称为Grinstead的猜想，并一直从各个角度进行研究以解决这一问题。到目前为止，只有证实其成功是在小溪数量相对明显的时候，通常认为预测成功的概率很低。今年的结果是，关于格林斯特的预测，我们已经成功地使用了计算证明来推动此预测最多的小溪数量至15。对于某些固定的$ \ omega（g）$。”在上述会议诉讼集合中已被接受为参考文件。我目前正在发布一篇论文，该论文将其开发为离散数学。作为一种基于理论的方法，我们一直在基于三个角度进行研究：组合图理论，整数编程和拓扑图理论。我们使用了必要的费用来购买期刊和书籍，以及在上述国际研讨会和国内学术会议上的演讲费用。此外，按照所应用，我根据需要在计算机周围购买了适当的消耗品，以在使用计算机模拟的情况下搜索反例，并且在实施计算机的实现范围内。