統一的な辺彩色因子理論の構築

本年度は，Tutte の因子定理の辺彩色版に関する研究を中心に行った結果，以下の研究成果が得られた．（１）次数和の高い 2 部グラフにおける panconnectivityについて：グラフのハミルトン閉路の存在性は，組合せ最適化と密接に関連しており，これに関する研究が多くなされている．本研究の対象である panconnectivity は，ハミルトン閉路の存在性より強い性質であり，グラフの連結性に関する概念である．Amar らは 2 部グラフの特別な場合において，指定した 2 頂点を結ぶような道で，短い 1 本の道を除いて，すべての長さの道が存在することを保障する最善の非隣接 2 頂点次数和条件を与えた．また，Du らは 2 部グラフのすべての場合において，指定した 2 頂点を結ぶような道で，短い 1 本の道を除いて，すべての長さの道が存在することを保障する最善の最小次数条件を与えた．本研究では，これらの共通の拡張として，2 部グラフのすべての場合において，指定した 2 頂点を結ぶような道で，短い 1 本の道を除いて，すべての長さの道が存在することを保障する最善の非隣接 2 頂点次数和条件を与えることができた．一年目・二年目に得られた知見に加えて，ここで得られた知見も三年目以降の研究に役立つものであると考えている．また，本研究成果は Graphs Combin. に掲載された．以上が，三年目に得られた成果である．

本年度は，Tutte の因子定理の辺彩色版に関する研究を中心に行った結果，以下の研究成果が得られた．（１）次数和の高い 2 部グラフにおける panconnectivityについて：グラフのハミルトン閉路の存在性は，組合せ最適化と密接に関連しており，これに関する研究が多くなされている．本研究の対象である panconnectivity は，ハミルトン閉路の存在性より強い性質であり，グラフの連結性に関する概念である．Amar らは 2 部グラフの特別な場合において，指定した 2 頂点を結ぶような道で，短い 1 本の道を除いて，すべての長さの道が存在することを保障する最善の非隣接 2 頂点次数和条件を与えた．また，Du らは 2 部グラフのすべての場合において，指定した 2 頂点を結ぶような道で，短い 1 本の道を除いて，すべての長さの道が存在することを保障する最善の最小次数条件を与えた．本研究では，これらの共通の拡張として，2 部グラフのすべての場合において，指定した 2 頂点を結ぶような道で，短い 1 本の道を除いて，すべての長さの道が存在することを保障する最善の非隣接 2 頂点次数和条件を与えることができた．一年目・二年目に得られた知見に加えて，ここで得られた知見も三年目以降の研究に役立つものであると考えている．また，本研究成果は Graphs Combin. に掲載された．以上が，三年目に得られた成果である．