グラフ理論における道と閉路と連結度に関する研究

图论中的路径、环路和连通性研究

• 批准号: 00J04528
• 负责人: 河原林 健一
• 金额: $ 1.92万
• 依托单位: Keio University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for JSPS Fellows
• 财政年份: 2000
• 资助国家: 日本
• 起止时间: 2000 至 2002
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-00J04528/
• 关键词: グラフ理論; 連結度; 道; 閉路; 彩色数; Hadaiger予想

本年度は、特に次のような研究を行った。・グラフ理論において、もっともむずかしいと思われる予想Hadaiger予想に対して、その最小反例は、ある程度、大きな連結度をもつことを証明した。このようなアプローチは、はじめて行われた。・グラフ理論において、もっとも深い理論とされるRobertson-Seymour理論の連結度が高いグラフへの応用を考え、点の数が大きければ、Dehse Graphをマイナーとしてもつことを証明した。・曲面上での最長サククルの長さ、最長パスの長さ等を、グラフマイナー理論を使って研究した。・4-連結グラフのRedractionを研究し、それらを使って今まで知られている定理の大きく改良、または簡単な証明を与えた。・5,6,7-連結グラフの縮約辺に関する研究を行った。・マッチングにかんする研究とfactorにかんする研究を行った。・3-正則グラフの研究。

This year's special research was conducted. The theory of love and understanding, the idea of love and understanding, the idea of Hadaiger, the smallest counterexample, the degree of love, and the degree of connection are all proved.このようなアプローチは、はじめて行われた。·The link degree of Robertson-Seymour theory is high, and the number of points is large. On the curved surface, the longest length, the longest length, etc. are studied. 4-The link between the two is a simple proof of the theorem and a large improvement of the theorem. 5, 6, 7-link linkage and reduction of the relevant research.·Research factor: 3-A study of regularization.

项目成果

K.Kawarabayashi, K.Ota, A.Saito: "Hamiltonian cycles in n-extendafle graphs"J.Graph Theory. 40. 75-82 (2002)

K.Kawarabayashi、K.Ota、A.Saito：“n-可扩展图中的哈密顿循环”J.图论。

K.Kawarabayashi: "K_4-factor in a graph"J.Graph Theory. 39. 111-128 (2002)

K.Kawarabayashi：“图中的 K_4 因子”J.Graph Theory。

K.Kawarabayashi: "Contractible edges and triangles in k-conn. graphs"J.Comin.Theory Ser.B. 85. 207-221 (2002)

K.Kawarabayashi：“k-conn. 图中的可收缩边和三角形”J.Comin.Theory Ser.B。

K.Kawarabayashi, H.Matsuda, Y.Oda, K.Ota: "Path factors in cubic graphs"J.Graph Theory. 39. 188-193 (2002)

K.Kawarabayashi、H.Matsuda、Y.Oda、K.Ota：“三次图中的路径因子”J.图论。

K.Kawarabayashi: "One or Two Disjoint Circuits Cover Independent Edges"J.Comb.Theory Ser.B. 84. 1-44 (2002)

K.Kawarabayashi：“一个或两个不相交的电路覆盖独立的边缘”J.Comb.Theory Ser.B。