Some Recent Progress and Applications in Graph Minor Theory |
| |
| Authors: | Ken-ichi Kawarabayashi Bojan Mohar |
| |
| Institution: | (1) The National Institute of Informatics, 2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo, 101-8430;(2) Department of Mathematics, Simon Fraser University, Burnaby, B.C, V5A 1S6 |
| |
| Abstract: | In the core of the seminal Graph Minor Theory of Robertson and Seymour lies a powerful theorem capturing the ``rough' structure
of graphs excluding a fixed minor. This result was used to prove Wagner's Conjecture that finite graphs are well-quasi-ordered
under the graph minor relation. Recently, a number of beautiful results that use this structural result have appeared. Some
of these along with some other recent advances on graph minors are surveyed.
Research partly supported by Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research, Grant number
16740044, by Sumitomo Foundation, by C & C Foundation and by Inoue Research Award for Young Scientists
Supported in part by the Research Grant P1–0297 and by the CRC program
On leave from: IMFM & FMF, Department of Mathematics, University of Ljubljana, Ljubljana, Slovenia |
| |
| Keywords: | Graph minor theory Tree-width Tree-decomposition Path-decomposition Complete graph minor Excluded minor Complete bipartite minor Connectivity Hadwiger Conjecture Grid minor Vortex structure Near embedding Graphs on surfaces |
| 本文献已被 SpringerLink 等数据库收录！ |
|
