Some Recent Progress and Applications in Graph Minor Theory

被引：0
作者：
Ken-ichi Kawarabayashi
Bojan Mohar
机构：
[1] The National Institute of Informatics,Department of Mathematics
[2] Simon Fraser University,undefined
来源：
Graphs and Combinatorics | 2007年 / 23卷
关键词：
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;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
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.
引用
收藏
页码：1 / 46
页数：45
相关论文
共 241 条
[1]  
Alon N.(1990)A separator theorem for non-planar graphs J. Amer. Math. Soc. 3 801-809
[2]  
Seymour P.D.(1981)A Kuratowski theorem for the projective plane J. Graph Theory 5 243-246
[3]  
Thomas R.(1989)A Kuratowski theorem for nonorientable surfaces J. Combin. Theory, Ser. B 46 173-231
[4]  
Archdeacon D.(1989)Linear time algorithms for NP-hard problems restricted to partial k-trees Discrete Appl. Math. 23 11-24
[5]  
Archdeacon D.(1994)Approximation algorithms for NP-complete problems on planar graphs J. Assoc. Comput. Mach. 41 153-180
[6]  
Huneke P.(1996)A linear-time algorithm for finding tree-decomposition of small treewidth SIAM J. Comput. 25 1305-1317
[7]  
Arnborg S.(2005)-minors in large graphs with given average degree Europ. J. Combinatorics 26 289-292
[8]  
Proskurowski A.(1996)Highly linked graphs Combinatorica 16 313-320
[9]  
Baker B.S.(1998)Proof of a conjecture of Mader, Erdős and Hajnal on topological complete subgraphs European J. Combin. 19 883-887
[10]  
Bodlaender H.L.(1996)Separating and nonseparating disjoint homotopic cycles in graph embeddings J. Comb. Theory, Ser. B 66 201-231
12345678910